The density conjecture for 5/2-critical graphs

About 12 years old · traced to

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.

References

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.