NSSW19's clustered colouring conjecture for minor-free graphs

From papers

For a graph HH, let MH\mathcal{M}_H be the class of graphs with no HH minor. Write \scalebox1.25\chi(MH)\raisebox{1.55pt}{\scalebox{1.25}{\chi}}_{\star}(\mathcal{M}_H) for its clustered chromatic number and td(H)\operatorname{\overline{td}}(H) for the connected treedepth of HH. NSSW19's conjecture. For every graph HH,

\scalebox1.25\chi(MH)2td(H)2.\raisebox{1.55pt}{\scalebox{1.25}{\chi}}_{\star}(\mathcal{M}_H)\leqslant 2\operatorname{\overline{td}}(H)-2.

The conjecture is an upper-bound analogue of the defective-colouring conjecture above. The source states that it remains open, while the paper proves matching lower-bound examples for suitable graphs of each connected treedepth.

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

Sergey Norin, Alex Scott and David R. Wood, “Clustered colouring of graph classes with bounded treedepth or pathwidth”, arXiv:2012.05554 (2022).

Solutions 0

No solutions have been posted yet.