Extremal Values of the Chromatic Number for a Given Degree Sequence

Abstract

For a degree sequence $d:d_1\ge \cdots \ge d_n$, we consider the smallest chromatic number ${\chi }_{\min }(d)$ and the largest chromatic number ${\chi }_{\max }(d)$ among all graphs with degree sequence $d$. We show that if $d_n\ge 1$, then ${\chi }_{\min }(d)\le \max \left\{3,d_1-\frac{n+1}{4d_1}+4\right\}$, and, if $\sqrt{n+\frac{1}{4}}-\frac{1}{2}>d_1\ge d_n\ge 1$, then ${\chi }_{\max }(d)=\underset{i\in [n]}{\max }\min \left\{i,d_i+1\right\}$. For a given degree sequence $d$ with bounded entries, we show that ${\chi }_{\min }(d)$, ${\chi }_{\max }(d)$, and also the smallest independence number ${\alpha }_{\min }(d)$ among all graphs with degree sequence $d$, can be determined in polynomial time.