The edge-density conjecture for Kk−2K_{k-2}-free kk-critical graphs

About 10 years old · traced to

Let k≥4k\ge 4, let GG be a graph, and write V(G)V(G) and E(G)E(G) for its vertex and edge sets. The graph GG is kk-critical if its chromatic number is kk and every proper subgraph has chromatic number less than kk; it is Kk−2K_{k-2}-free if it contains no clique on k−2k-2 vertices.

Edge-density conjecture. For every k≥4k\ge 4, there exists ϵk>0\epsilon_k>0 such that if GG is a kk-critical Kk−2K_{k-2}-free graph, then

∣E(G)∣≥(k2−1k−1+ϵk)∣V(G)∣−k(k−3)2(k−1).|E(G)|\ge \left(\frac{k}{2}-\frac{1}{k-1} + \epsilon_k\right)|V(G)| - \frac{k(k-3)}{2(k-1)}.

The conjecture asks whether excluding Kk−2K_{k-2} improves the tight general lower bound of Kostochka and Yancey for the number of edges in a kk-critical graph; excluding Kk−1K_{k-1} is known not to improve that bound. The surrounding discussion identifies this as an open direction, while related asymptotic results are known for fixed-size excluded cliques.

References

Primary source

Luke Postle, “On the Minimum Number of Edges in Triangle-Free 5-Critical Graphs”, arXiv:1602.03098 (2017).

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.