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

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

V 1, V 2, \dots, V k

such that each

V i

is an independent set for

G

and such that for each pair of distinct sets

V i, V j, V i \cup V j

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

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 $O\left(|V|/{\sqrt {\log |V|}}\right)$ approximation ratio.^[3]

Special classes of graphs

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 ${\sqrt {n2^{n}}}$ , but the constant of proportionality is not known precisely.^[7]

References

^ Jump up to: ^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.
^ Jump up to: ^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.
^ Jump up to: ^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

A compendium of NP optimization problems
A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards

[gj-1] Jump up to: ^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.

[fhhm-2] Jump up to: ^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.

[cv-3] Jump up to: ^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.

[4] 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.

[5] 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.

[6] Yannakakis, M.; Gavril, F. (1980), "Edge dominating sets in graphs", SIAM Journal on Applied Mathematics, 38 (3): 364–372, doi:10.1137/0138030.

[7] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]