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:
“In this century the writer has carried on a conversation with madness. We might almost say of the twentieth-century writer that he aspires to madness. Some have made it, of course, and they hold special places in our regard. To a writer, madness is a final distillation of self, a final editing down. It’s the drowning out of false voices.”
—Don Delillo (b. 1926)
“... too much attention is paid to dress by those who have neither the excuse of ample means nor of social claims.... The injury done by this state of things to the morals and the manners of our lower classes is incalculable.”
—Mrs. H. O. Ward (1824–1899)