The local track-number conjecture for planar graphs
The local track-number conjecture for planar graphs
Let be a planar graph, and let its local track-number be the minimum number of tracks in an injective track cover such that every vertex belongs to at most that many tracks.
Local track-number conjecture. The local track-number of is at most .
The source identifies this as the only unresolved entry in its table of covering-number questions. It notes that the bound is known for bipartite planar graphs and for planar graphs of treewidth at most , while the general planar case remains open.
Sources & referencesView supporting material
Primary source
Kolja Knauer and Torsten Ueckerdt, “Three ways to cover a graph”, arXiv:1205.1627 (2015).
Additional references
2 papers in this index state this conjecture (2010–2012). The statement above is taken from the most recent of them; the others are arXiv:1009.2861.
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.