Liu and Postle's density conjecture for triangle-free 4-critical graphs

A graph GG is 4-critical if it is 44-colourable but every proper subgraph is 33-colourable; it is triangle-free if it contains no subgraph isomorphic to K3K_3. Write v(G)=V(G)v(G)=|V(G)| and e(G)=E(G)e(G)=|E(G)|. Liu and Postle's density conjecture. If GG is a 44-critical triangle-free graph, then

e(G)5v(G)+53.e(G) \geq \frac{5v(G)+5}{3}.

This conjecture seeks a sharper lower-order improvement to the general Kostochka–Yancey edge bound for critical graphs after excluding triangles. The source gives no resolution status for the conjecture.

Sources & referencesView supporting material

Primary source

Benjamin Moore and Evelyne Smith-Roberge, “A density bound for triangle-free 4-critical graphs”, arXiv:2012.01503 (2022).

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.