The edge-density conjecture for -free -critical graphs
The edge-density conjecture for -free -critical graphs
Let , let be a graph, and write and for its vertex and edge sets. The graph is -critical if its chromatic number is and every proper subgraph has chromatic number less than ; it is -free if it contains no clique on vertices.
Edge-density conjecture. For every , there exists such that if is a -critical -free graph, then
The conjecture asks whether excluding improves the tight general lower bound of Kostochka and Yancey for the number of edges in a -critical graph; excluding 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.