Browsing Combinatorics and Optimization by Supervisor "Haxell, Penelope"
Now showing items 1-1 of 1
-
On Finding Large Cliques when the Chromatic Number is close to the Maximum Degree
(University of Waterloo, 2021-12-23)We prove that every graph G with chromatic number χ(G) = ∆(G) − 1 and ∆(G) ≥ 66 contains a clique of size ∆(G) − 17. Our proof closely parallels a proof from Cranston and Rabern, who showed that graphs with χ = ∆ and ∆ ≥ ...