Polynomial weak colouring-number conjecture for Ks,tK^*_{s,t}-minor-free graphs

From papers

For positive integers ss and tt, let Ks,tK^*_{s,t} be the complete join of KsK_s and Kt\overline{K_t}. A graph is Ks,tK^*_{s,t}-minor-free if it contains no minor isomorphic to Ks,tK^*_{s,t}. For a graph GG and integer r1r\geqslant1, let wcolr(G)\operatorname{wcol}_r(G) denote its weak rr-colouring number.

Polynomial weak colouring-number conjecture. There exists a function ff such that for every Ks,tK^*_{s,t}-minor-free graph GG and every r1r\geqslant1,

wcolr(G)f(s,t)rs.\operatorname{wcol}_r(G)\leqslant f(s,t)\,r^s.

The conjecture would generalise the displayed bounds for K2,tK^*_{2,t}- and K3,tK^*_{3,t}-minor-free graphs and would give polynomial weak colouring-number bounds for these minor-closed graph classes. The source gives no resolution status.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

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).

Solutions 0

No solutions have been posted yet.