Chromatic coloring with a maximum color class Original Research Article

Let image be any graph, and also let image, image and image denote the maximum degree, the chromatic number and the independence number of image, respectively. A chromatic coloring of image is a proper coloring of image using image colors. A color class in a proper coloring of image is maximum if it has size image. In this paper, we prove that if a graph image (not necessarily connected) satisfies image, then there exists a chromatic coloring of image in which some color class is maximum. This cannot be guaranteed if image. We shall also give some other extensions.