Ossona de Mendez–Oum–Wood defective colouring conjecture

For a graph class G\mathcal{G}, let χΔ(G)\chi_{\Delta}(\mathcal{G}) be the minimum integer kk such that, for some integer dd, every graph in G\mathcal{G} is kk-colourable with defect dd. For a graph HH, let MH\mathcal{M}_H be the class of HH-minor-free graphs, and let td(H)\operatorname{\overline{td}}(H) denote the connected tree-depth of HH. Ossona de Mendez–Oum–Wood's conjecture. For every graph HH,

χΔ(MH)=td(H)1.\chi_{\Delta}(\mathcal{M}_H)=\operatorname{\overline{td}}(H)-1.

The conjecture is a defective-colouring analogue of Hadwiger's conjecture. The lower bound is proved, and the upper bound is known when td(H)3\operatorname{\overline{td}}(H)\leqslant 3, when HH is complete bipartite, and when H=KtH=K_t; the general upper bound remains open.

Sources & referencesView supporting material

Primary source

Sergey Norin, Alex Scott, Paul Seymour and David R. Wood, “Clustered Colouring in Minor-Closed Classes”, arXiv:1708.02370 (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.