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

From papers

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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.