Special Classes of Graphs
For any tree with maximum degree Δ, the equitable chromatic number is at most
with the worst case occurring for a star. However, most trees have significantly smaller equitable chromatic number: if a tree with n vertices has Δ ≤ n/3 − O(1), then it has an equitable coloring with only three colors. Furmańczyk (2006) studies the equitable chromatic number of graph products.
Read more about this topic: Equitable Coloring
Famous quotes containing the words special and/or classes:
“When, in some obscure country town, the farmers come together to a special town meeting, to express their opinion on some subject which is vexing to the land, that, I think, is the true Congress, and the most respectable one that is ever assembled in the United States.”
—Henry David Thoreau (1817–1862)
“Genocide begins, however improbably, in the conviction that classes of biological distinction indisputably sanction social and political discrimination.”
—Andrea Dworkin (b. 1946)