Complete coloring

From Wikipedia, the free encyclopedia

You have new messages (last change).

In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. The achromatic number ψ(G) of a graph G is the maximum number of colors possible in any complete coloring of G. 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 less disjoint sets V_1,V_2,\ldots,V_k such that each Vi 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 less than a given number is NP-complete, as shown by Yannakakis and Gavril in 1978 by transformation from the minimum maximal matching problem. It is still NP-complete even when restricted to graphs that are the complement of a bipartite graph (that is, graphs having no independent set of more than two vertices).

The optimization problem permits approximation and is approximable within O\left(|V|/\sqrt{\log |V|}\right)

[edit] References

[edit] External links

  • [1] A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards


This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../c/o/m/Complete_coloring.html"