Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649959 | Discrete Mathematics | 2008 | 5 Pages |
Abstract
Let GG be any graph, and also let Δ(G)Δ(G), χ(G)χ(G) and α(G)α(G) denote the maximum degree, the chromatic number and the independence number of GG, respectively. A chromatic coloring of GG is a proper coloring of GG using χ(G)χ(G) colors. A color class in a proper coloring of GG is maximum if it has size α(G)α(G). In this paper, we prove that if a graph GG (not necessarily connected) satisfies χ(G)≥Δ(G)χ(G)≥Δ(G), then there exists a chromatic coloring of GG in which some color class is maximum. This cannot be guaranteed if χ(G)<Δ(G)χ(G)<Δ(G). We shall also give some other extensions.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Bor-Liang Chen, Kuo-Ching Huang, Chih-Hung Yen,