Bounded-path partition conjecture for -minor-free graphs
Bounded-path partition conjecture for -minor-free graphs
For positive integers and , let be the complete join of and . A connected partition of width is a partition into connected subgraphs with quotient width in the sense used by the source. A shortest path is a path shortest in the indicated vertex-deleted graph.
Bounded-path partition conjecture. For all , there exists an integer such that every -minor-free graph has a connected partition with width , such that for ,
where and each is a shortest path in
The source says that this conjecture would imply the polynomial weak colouring-number conjecture together with the preceding BFS-colouring lemma. Its resolution status is not given.
Sources & referencesView supporting material
Primary source
Jan van den Heuvel and David R. Wood, “Improper Colourings inspired by Hadwiger's Conjecture”, arXiv:1704.06536 (2018).
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.