## 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.

### MSC:

 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: