The density conjecture for 5/2-critical graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.