Linear vertex deletion conjecture for bounded boxicity of surface graphs
Linear vertex deletion conjecture for bounded boxicity of surface graphs
Let be a graph embedded on a surface of Euler genus . The boxicity of a graph is the minimum dimension in which it can be represented as the intersection graph of axis-parallel boxes.
Linear vertex deletion conjecture. There is a constant such that, for every graph embedded on a surface of Euler genus , at most vertices can be removed so that the resulting graph has boxicity at most .
The conjecture is a surface-graph variant of the preceding conjecture for locally planar graphs. The supplied source gives no evidence that it has been resolved; it would in particular provide a linear-size deletion bound depending on the Euler genus.
Sources & referencesView supporting material
Primary source
Louis Esperet, “Box representations of embedded graphs”, arXiv:1512.02381 (2016).
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
Sign in to submit a solution.
No solutions have been posted yet.