Given a graphic degree sequence $D$, let $\chi(D)$ (respectively $\omega(D)$, $h(D)$, and $H(D)$) denote the maximum value of the chromatic number (respectively, the size of the largest clique, largest clique subdivision, and largest clique minor) taken over all graphs whose degree sequence is $D$. It is proved that $\chi(D)\le h(D)$.
Moreover, it is shown that a subdivision of a clique of order $\chi(D)$ exists where each edge is subdivided at most once and the set of all subdivided edges forms a collection of disjoint stars. This bound is an analogue of the Haj\'os Conjecture for degree sequences and, in particular, settles a conjecture of Neil Robertson that degree sequences satisfy the bound $\chi(D)\le H(D)$ (which is related to the Hadwiger Conjecture). It is also proved that $\chi(D)\le \frac{6}{5}\omega(D)+\frac{3}{5}$ and that $\chi(D) \le
\frac{4}{5}\omega(D) + \frac{1}{5}\Delta(D) + 1$, where $\Delta(D)$ denotes the maximum degree in $D$. The latter inequality is a strengthened version of a conjecture of Bruce Reed. All derived inequalities are best possible.
This is a joint work with Zdenek Dvorak.
Copyright. All Rights Reserved.