← All problems

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

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
  1. 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.