Special Classes of Graphs
The NP-completeness of the achromatic number problem holds also for some special classes of graphs: bipartite graphs, complements of bipartite graphs (that is, graphs having no independent set of more than two vertices), cographs and interval graphs, and even for trees.
For complements of trees, the achromatic number can be computed in polynomial time. For trees, it can be approximated to within a constant factor.
The achromatic number of an n-dimensional hypercube graph is known to be proportional to, but the constant of proportionality is not known precisely.
Read more about this topic: Complete Coloring
Famous quotes containing the words special and/or classes:
“Jack: A politician, huh?
Editor: Oh, county treasurer or something like that.
Jack: What’s so special about him?
Editor: They say he’s an honest man.”
—Robert Rossen (1908–1966)
“Genocide begins, however improbably, in the conviction that classes of biological distinction indisputably sanction social and political discrimination.”
—Andrea Dworkin (b. 1946)