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:
“The great rule: If the little bit you have is nothing special in itself, at least find a way of saying it that is a little bit special.”
—G.C. (Georg Christoph)
“There were three classes of inhabitants who either frequent or inhabit the country which we had now entered: first, the loggers, who, for a part of the year, the winter and spring, are far the most numerous, but in the summer, except for a few explorers for timber, completely desert it; second, the few settlers I have named, the only permanent inhabitants, who live on the verge of it, and help raise supplies for the former; third, the hunters, mostly Indians, who range over it in their season.”
—Henry David Thoreau (1817–1862)