Article ID Journal Published Year Pages File Type
4649959 Discrete Mathematics 2008 5 Pages PDF
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
, , ,