The local track-number conjecture for planar graphs

Let GG 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 GG is at most 33.

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 33, 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

Never refreshed

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.