DMS Combinatorics Seminar

Speaker: Jessica McDonald, Auburn University

Title: Cliques and High Odd Holes in Graphs with Chromatic Number Equal to Maximum Degree

Abstract: It is easy to show that every graph \(G\) satisfies \(\chi(G)\leq \Delta(G)+1\), where  \(\chi(G), \Delta(G)\) denote the chromatic number and maximum degree of \(G\), respectively. Brooks' Theorem says that if a connected graph \(G\) has \(\chi(G)=\Delta(G)+1\), then \(G\) is either  \(K_{\Delta(G)+1}\) or an odd cycle. In this talk we discuss a new, uniform, and self-contained proof of the following result: if \(G\) is a connected graph with \(\chi(G) = \Delta(G)\) and \(G\neq \overline{C_7}\), then \(G\) contains either \(K_{\Delta(G)}\) or an odd hole where every vertex has degree at least \(\Delta(G)-1\) in \(G\). This was previously proved in a series of two papers by Chen, Lan, Lin, and Zhou, who used the Strong Perfect Graph Theorem for the cases \(\Delta(G)=4, 5, 6\).

This is joint work with Rachel Galindo and Songling Shan.