In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes. The achromatic numberψ(G) of a graph G is the maximum number of colors possible in any complete coloring of G.
Complete coloring of the Clebsch graph with 8 colors. Every pair of colors appears on at least one edge. No complete coloring with more colors exists: in any 9-coloring some color would appear only at one vertex, and there would not be enough neighboring vertices to cover all pairs involving that color. Therefore, the achromatic number of the Clebsch graph is 8.
A complete coloring is the opposite of a harmonious coloring, which requires every pair of colors to appear on at most one pair of adjacent vertices.
INSTANCE: a graph G = (V, E) and positive integer k
QUESTION: does there exist a partition of V into k or more disjoint setsV1, V2, …, Vk such that each Vi is an independent set for G and such that for each pair of distinct sets Vi, Vj, Vi ∪ Vj is not an independent set.
Determining the achromatic number is NP-hard; determining if it is greater than a given number is NP-complete, as shown by Yannakakis and Gavril in 1978 by transformation from the minimum maximal matching problem.[1]
Note that any coloring of a graph with the minimum number of colors must be a complete coloring, so minimizing the number of colors in a complete coloring is just a restatement of the standard graph coloring problem.
Algorithmsedit
For any fixed k, it is possible to determine whether the achromatic number of a given graph is at least k, in linear time.[2]
The optimization problem permits approximation and is approximable within a approximation ratio.[3]
For complements of trees, the achromatic number can be computed in polynomial time.[6] For trees, it can be approximated to within a constant factor.[3]
The achromatic number of an n-dimensional hypercube graph is known to be proportional to , but the constant of proportionality is not known precisely.[7]
^ abFarber, M.; Hahn, G.; Hell, P.; Miller, D. J. (1986), "Concerning the achromatic number of graphs", Journal of Combinatorial Theory, Series B, 40 (1): 21–39, doi:10.1016/0095-8956(86)90062-6.
^ abChaudhary, Amitabh; Vishwanathan, Sundar (2001), "Approximation algorithms for the achromatic number", Journal of Algorithms, 41 (2): 404–416, CiteSeerX10.1.1.1.5562, doi:10.1006/jagm.2001.1192, S2CID 9817850.
^Bodlaender, H. (1989), "Achromatic number is NP-complete for cographs and interval graphs", Inf. Process. Lett., 31 (3): 135–138, doi:10.1016/0020-0190(89)90221-4, hdl:1874/16576.
^Manlove, D.; McDiarmid, C. (1995), "The complexity of harmonious coloring for trees", Discrete Applied Mathematics, 57 (2–3): 133–144, doi:10.1016/0166-218X(94)00100-R.
^Yannakakis, M.; Gavril, F. (1980), "Edge dominating sets in graphs", SIAM Journal on Applied Mathematics, 38 (3): 364–372, doi:10.1137/0138030.
^Roichman, Y. (2000), "On the Achromatic Number of Hypercubes", Journal of Combinatorial Theory, Series B, 79 (2): 177–182, doi:10.1006/jctb.2000.1955.
External linksedit
A compendium of NP optimization problems
by Keith Edwards
December 18, 2023
complete, coloring, graph, theory, complete, coloring, vertex, coloring, which, every, pair, colors, appears, least, pair, adjacent, vertices, equivalently, complete, coloring, minimal, sense, that, cannot, transformed, into, proper, coloring, with, fewer, col. In graph theory a complete coloring is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices Equivalently a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes The achromatic number ps G of a graph G is the maximum number of colors possible in any complete coloring of G Complete coloring of the Clebsch graph with 8 colors Every pair of colors appears on at least one edge No complete coloring with more colors exists in any 9 coloring some color would appear only at one vertex and there would not be enough neighboring vertices to cover all pairs involving that color Therefore the achromatic number of the Clebsch graph is 8 A complete coloring is the opposite of a harmonious coloring which requires every pair of colors to appear on at most one pair of adjacent vertices Contents 1 Complexity theory 2 Algorithms 3 Special classes of graphs 4 References 5 External linksComplexity theory editFinding ps G is an optimization problem The decision problem for complete coloring can be phrased as INSTANCE a graph G V E and positive integer k QUESTION does there exist a partition of V into k or more disjoint sets V1 V2 Vk such that each Vi is an independent set for G and such that for each pair of distinct sets Vi Vj Vi Vj is not an independent set Determining the achromatic number is NP hard determining if it is greater than a given number is NP complete as shown by Yannakakis and Gavril in 1978 by transformation from the minimum maximal matching problem 1 Note that any coloring of a graph with the minimum number of colors must be a complete coloring so minimizing the number of colors in a complete coloring is just a restatement of the standard graph coloring problem Algorithms editFor any fixed k it is possible to determine whether the achromatic number of a given graph is at least k in linear time 2 The optimization problem permits approximation and is approximable within a O V log V displaystyle O left V sqrt log V right nbsp approximation ratio 3 Special classes of graphs editThe NP completeness of the achromatic number problem holds also for some special classes of graphs bipartite graphs 2 complements of bipartite graphs that is graphs having no independent set of more than two vertices 1 cographs and interval graphs 4 and even for trees 5 For complements of trees the achromatic number can be computed in polynomial time 6 For trees it can be approximated to within a constant factor 3 The achromatic number of an n dimensional hypercube graph is known to be proportional to n 2 n displaystyle sqrt n2 n nbsp but the constant of proportionality is not known precisely 7 References edit a b Michael R Garey and David S Johnson 1979 Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman ISBN 978 0 7167 1045 5 A1 1 GT5 pg 191 a b Farber M Hahn G Hell P Miller D J 1986 Concerning the achromatic number of graphs Journal of Combinatorial Theory Series B 40 1 21 39 doi 10 1016 0095 8956 86 90062 6 a b Chaudhary Amitabh Vishwanathan Sundar 2001 Approximation algorithms for the achromatic number Journal of Algorithms 41 2 404 416 CiteSeerX 10 1 1 1 5562 doi 10 1006 jagm 2001 1192 S2CID 9817850 Bodlaender H 1989 Achromatic number is NP complete for cographs and interval graphs Inf Process Lett 31 3 135 138 doi 10 1016 0020 0190 89 90221 4 hdl 1874 16576 Manlove D McDiarmid C 1995 The complexity of harmonious coloring for trees Discrete Applied Mathematics 57 2 3 133 144 doi 10 1016 0166 218X 94 00100 R Yannakakis M Gavril F 1980 Edge dominating sets in graphs SIAM Journal on Applied Mathematics 38 3 364 372 doi 10 1137 0138030 Roichman Y 2000 On the Achromatic Number of Hypercubes Journal of Combinatorial Theory Series B 79 2 177 182 doi 10 1006 jctb 2000 1955 External links editA compendium of NP optimization problems A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards Retrieved from https en wikipedia org w index php title Complete coloring amp oldid 1096565282, wikipedia, wiki, book, books, library,
