Sparsity of clique-bounded critical graphs

Question 1.3 · arXiv:1810.06704

arXiv Question high confidence— first stated 2018-10-15

Authors: Marthe Bonamy, Thomas Perrett, Luke Postle

Status partial medium confidence

Question 1.3 asks for the optimal δ(ε,α) quantifying how sparse a critical graph with bounded clique number must be — Step 1 of the King–Reed strategy for Reed's conjecture. A 2020 master's thesis by Kroeker (supervised by Postle at UWaterloo) directly addresses sparsity of list-critical graphs with small clique number, deriving new density lemmas by embedding the graph in a complete multipartite graph with many parts of size three. Kelly and Postle (arXiv:1911.02672) separately prove an improved lower bound on the density of k-critical graphs with clique number less than k/2. Neither work fully determines the optimal δ(ε,α), so the question remains open.

Cited literature (2)

partial A local epsilon version of Reed's Conjecture (2019)

Tom Kelly, Luke Postle · arXiv preprint (also published in Journal of Combinatorial Theory, Series B per search results) · arXiv:1911.02672

Proves a significantly improved lower bound on the average degree of k-critical graphs with clique number less than k/2, giving partial progress on the density side of the sparsity-density paradigm underlying Question 1.3.
partial Sparsity in Critical Graphs with Small Clique Number (2020)

Matthew Eliot Kroeker · Master's thesis, University of Waterloo

Directly addresses sparsity of list-critical graphs with small clique number (the precise setting of Question 1.3), deriving new density lemmas via complete multipartite embeddings and an unbalanced list-colouring argument, supervised by Luke Postle.

Reviewer notes. The Kroeker thesis (2020) is the most directly relevant follow-up and is confirmed to address the sparsity of critical graphs with small clique number (Chapter 3: Sparsity and Antitriangles). A 2023 Combinatorica paper by Kelly–Postle titled 'On the Density of Critical Graphs with No Large Cliques' was found in search results but could not be verified via WebFetch (Springer paywall redirect). The exact value of δ(ε,α) asked in Question 1.3 appears not yet determined in the published literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Let $G$ be a $\lfloor (1-\varepsilon)(\Delta(G)+1) \rfloor + 1$-critical graph with $\omega(G) \leq (1-\alpha)(\Delta(G)+1)$. What is the largest $\delta = \delta(\varepsilon,\alpha)$, such that $G$ is $\delta$-sparse?

Context

This question isolates the first of two steps in the King–Reed proof strategy for Reed's conjecture: showing that a graph which is critical with respect to a list assignment and has bounded clique number must have sparse neighbourhoods. Improving $\delta$ directly strengthens the $\varepsilon$ achievable in Theorem 1.2.

Notes. PDF source; statement is clearly readable.

Source paper

Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications
Marthe Bonamy, Thomas Perrett, Luke Postle · 2018-10-15
https://arxiv.org/abs/1810.06704 PDF source