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:
“Nature is a setting that fits equally well a comic or a mourning piece. In good health, the air is a cordial of incredible virtue. Crossing a bare common, in snow puddles, at twilight, under a clouded sky, without having in my thoughts any occurrence of special good fortune, I have enjoyed a perfect exhilaration. I am glad to the brink of fear.”
—Ralph Waldo Emerson (1803–1882)
“By his very success in inventing labor-saving devices, modern man has manufactured an abyss of boredom that only the privileged classes in earlier civilizations have ever fathomed.”
—Lewis Mumford (1895–1990)