Postle's density conjecture for clique-free critical graphs

Let k4k\geq 4 and let GG be a kk-critical graph, meaning that χ(G)=k\chi(G)=k while every proper subgraph has chromatic number k1k-1. Write e(G)=E(G)e(G)=|E(G)| and v(G)=V(G)v(G)=|V(G)|.

Postle's density conjecture. For every k4k\geq 4, there exists εk>0\varepsilon_k>0 such that if GG does not contain a Kk2K_{k-2} subgraph, then

e(G)(k21k1+εk)v(G)k(k3)2(k1).e(G)\geq\left(\frac{k}{2}-\frac{1}{k-1}+\varepsilon_k\right)v(G)-\frac{k(k-3)}{2(k-1)}.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.