Complete coloring
In graph theory, a complete coloring is a (proper) 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.
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.
Complexity theory
[edit]Finding ψ(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
[edit]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]
Special classes of graphs
[edit]The 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 , 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.