Postle's density conjecture for clique-free critical graphs
Postle's density conjecture for clique-free critical graphs
Let and let be a -critical graph, meaning that while every proper subgraph has chromatic number . Write and .
Postle's density conjecture. For every , there exists such that if does not contain a subgraph, then
This strengthens the Kostochka–Yancey lower bound for critical graphs under the absence of a large clique; the source presents it as a conjecture of Luke Postle, and no resolution is given here.
Sources & referencesView supporting material
Primary source
Benjamin Moore, “Sparse 4-critical graphs have low circular chromatic number”, arXiv:2007.15556 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.