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:
“I have the handicap of being born with a special language to which I alone have the key.”
—Gustave Flaubert (1821–1880)
“Genocide begins, however improbably, in the conviction that classes of biological distinction indisputably sanction social and political discrimination.”
—Andrea Dworkin (b. 1946)