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
Download: Adobe PDF Compressed Postscript
Compressed Postscript 
