Extremal Values of the Chromatic Number for a Given Degree Sequence

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)\leq \max\left{ 3,d_1-\frac{n+1}{4d_1}+4\right}$,and,if$\sqrt{n+\frac{1}{4}}-\frac{1}{2}>d_1\geq d_n\geq 1$,then$\chi_{\max}(d)=\max\limits_{i\in [n]}\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.