Graphs with χ = Δ have Big Cliques

Let G be a graph with maximum degree Δ≥3. Brooks' Theorem says that if G has chromatic number Δ+1, then G has a clique on Δ+1 vertices; otherwise G has chromatic number at most Δ. In 1977 Borodin and Kostochka conjectured that if G is a graph with maximum degree Δ≥9 and chromatic number Δ, then G has a clique on Δ vertices. For maximum degree Δ≥13, we prove that if G has chromatic number Δ, then G has a clique on at least Δ-3 vertices. This is joint work with Landon Rabern.

Event Topic

Discrete Applied Math Seminar