The bounded-boxicity conjecture for large-edgewidth graphs on a fixed surface

About 15 years old · traced to

Let GG be a graph embedded in a fixed surface Σ\Sigma. The edgewidth of GG is the length, measured by the number of edges, of a shortest noncontractible cycle in GG.

Large-edgewidth boxicity conjecture. There exists an integer eΣe_\Sigma such that every graph GG embeddable on Σ\Sigma with edgewidth at least eΣe_\Sigma has boxicity at most three.

Kawarabayashi and Mohar proved that graphs embeddable in a fixed surface with sufficiently large edgewidth are acyclically 7-colorable, which yields boxicity at most 42. The conjecture proposes the stronger bound three.

References

Primary source

Louis Esperet and Gwenaël Joret, “Boxicity of graphs on surfaces”, arXiv:1107.1953 (2012).

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.