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

About 6 years old · traced to

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.

References

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.