NSSW19's clustered colouring conjecture for minor-free graphs

About 6 years old · traced to

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.

References

Primary source

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

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.