Postle's density conjecture for clique-free critical graphs

At least 5 years old · documented by

Let k≥4k\geq 4 and let GG be a kk-critical graph, meaning that χ(G)=k\chi(G)=k while every proper subgraph has chromatic number k−1k-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 k≥4k\geq 4, there exists εk>0\varepsilon_k>0 such that if GG does not contain a Kk−2K_{k-2} subgraph, then

e(G)≥(k2−1k−1+εk)v(G)−k(k−3)2(k−1).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.

References

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.