Bounds for the chromatic number of graphs with partial information. (English) Zbl 1014.05023

Bounds for the chromatic number, clique number, and independence number of a graph \(G\) are obtained in terms of the number of vertices and edges of \(G\), and in terms of \(G\)’s degree sequence. The tightness of these bounds, which include several known bounds but also a new upper bound for the chromatic number, is examined and the structure of extreme examples attaining the bounds are given.


05C15 Coloring of graphs and hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C07 Vertex degrees
05C35 Extremal problems in graph theory
Full Text: DOI