The density conjecture for 5/2-critical graphs
Let be a -critical graph, meaning that has no circular -coloring (equivalently, no homomorphism to ), while every proper subgraph of has such a coloring. Write and .
The density conjecture for -critical graphs. If is a -critical graph, then
The conjectured bound is tight for the graphs arising from the stated Ore construction and for the triangle. It is motivated by the asymptotic edge density of those examples, but the source does not state that the bound has been proved or disproved.
References
Primary source
Zdenek Dvorak and Luke Postle, “Density of 5/2-critical graphs”, arXiv:1411.6668 (2014).
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
No solutions have been posted yet.