Bounded-path partition conjecture for Ks,tK^*_{s,t}-minor-free graphs

For positive integers ss and tt, let Ks,tK^*_{s,t} be the complete join of KsK_s and Kt\overline{K_t}. A connected partition of width s1s-1 is a partition H1,,HH_1,\dots,H_\ell into connected subgraphs with quotient width s1s-1 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 ts1t\geqslant s\geqslant1, there exists an integer pp such that every Ks,tK^*_{s,t}-minor-free graph GG has a connected partition H1,,HH_1,\dots,H_\ell with width s1s-1, such that for i[]i\in[\ell],

V(Hi)=V(Pi,1)V(Pi,pi),V(H_i)=V(P_{i,1})\cup\dots\cup V(P_{i,p_i}),

where pipp_i\leqslant p and each Pi,jP_{i,j} is a shortest path in

G((V(H1)V(Hi1))(V(Pi,1)V(Pi,j1))).G-\Bigl(\bigl(V(H_1)\cup\dots\cup V(H_{i-1})\bigr)\cup\bigl(V(P_{i,1})\cup\dots\cup V(P_{i,j-1})\bigr)\Bigr).

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

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.