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.
References
Primary source
Louis Esperet and Gwenaël Joret, “Boxicity of graphs on surfaces”, arXiv:1107.1953 (2012).
Progress summary
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.