DMS Combinatorics Seminar

Speaker: Rachel Galindo (Auburn University)

Title: Vertex Coloring and Clique Containment

Abstract: This talk will consist of two separate, but related topics. 

The first: An equivalent version of the Borodin-Kostochka Conjecture, due to Cranston and Rabern, says that any graph with \(\chi = \Delta = 9\) contains \(K_3 \lor E_6\) as a subgraph. In this talk, we will discuss several results in support of this conjecture, where vertex-criticality and forbidden substructure conditions get us either close or all the way to containing \(K_3 \lor E_6\).

The second: The Ore Degree is a graph parameter which has been proven to serve as an upper bound for the chromatic number. We define two new Ore-type graph parameters and present preliminary results towards showing they also can serve as upper bounds on \(\chi\).