The density conjecture for 5/2-critical graphs

Let GG be a 5/25/2-critical graph, meaning that GG has no circular 5/25/2-coloring (equivalently, no homomorphism to C5C_5), while every proper subgraph of GG has such a coloring. Write n(G)=V(G)n(G)=|V(G)| and e(G)=E(G)e(G)=|E(G)|.

The density conjecture for 5/25/2-critical graphs. If GG is a 5/25/2-critical graph, then

14n(G)11e(G)9.14n(G)-11e(G)\le 9.

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 14/1114/11 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

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.