Dense and high degree structures in graphs with chromatic number equal to maximum degree

Abstract

It is well-known that for any graph $G$, $\chi(G)\leq \Delta(G)+1$; Brooks’ Theorem says that all graphs meeting this upper bound must contain either $K_{\Delta(G)+1}$ or be an odd cycle. The Borodin-Kostochka Conjecture, from 1977, posits that all graphs with $\chi(G)=\Delta(G)$ (with $\Delta(G)\geq 9$) must contain a $K_{\Delta(G)}$. This thesis has two main lines of work, both of which are related to the Borodin-Kostochka Conjecture. In the first, we focus on vertex-critical graphs with $\chi(G)=\Delta(G)=9$ and prove that, given some forbidden subgraph conditions, we can get close (in some sense) to containing a $K_{\Delta(G)}$ . In the second main topic of this thesis, we prove that every graph $G$ with $\chi(G) = \Delta(G)$ (and $\Delta(G)\neq 5, 6$) contains either a “high’’ $K_{\omega(G)}$ or a “high” odd hole, where ``high'' means that the vertices have average degree at least $\Delta(G)-1$. This theorem is a weakening of the Borodin-Kostochka Conjecture when $\Delta(G)\geq 9$; when $\Delta(G)\leq 8$ there are examples showing that both the high odd hole and the high $K_{\omega(G)}$ are needed in the statement of the theorem.