The bounded-boxicity conjecture for large-edgewidth graphs on a fixed surface
The bounded-boxicity conjecture for large-edgewidth graphs on a fixed surface
Let be a graph embedded in a fixed surface . The edgewidth of is the length, measured by the number of edges, of a shortest noncontractible cycle in .
Large-edgewidth boxicity conjecture. There exists an integer such that every graph embeddable on with edgewidth at least 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
Sign in to submit a solution.
No solutions have been posted yet.