ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. LXXI, 1(2002)
p. 1

A NOTE ON UPPER BOUND FOR CHROMATIC\\ NUMBER OF A GRAPH
L. Stacho

Abstract.  Let $$G$$ be a graph and let $$s$$ be the maximum number of vertices of the same degree, each at least $$(\Delta (G)+2)/2$$, where $$\Delta \left( G\right)$$ is the maximum degree in $$G$$. We show that the chromatic number $$\chi \left( G\right) \leq \left\lceil \frac s s+1 \left( \Delta \left( G\right) +2\right) \right\rceil$$.

AMS subject classification:  05C15 05C07
Keywords:  chromatic number, degree sequence, maximum degree