The edge-density conjecture for Kk2K_{k-2}-free kk-critical graphs

Let k4k\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 Kk2K_{k-2}-free if it contains no clique on k2k-2 vertices.

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

E(G)(k21k1+ϵk)V(G)k(k3)2(k1).|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 Kk2K_{k-2} improves the tight general lower bound of Kostochka and Yancey for the number of edges in a kk-critical graph; excluding Kk1K_{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.

Sources & referencesView supporting material

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.