Odd-minor clustered and defective colouring conjecture

Let HH be a graph, let GHodd\mathcal{G}_H^{\text{odd}} be the class of graphs with no HH odd-minor, let td(H)\operatorname{\overline{td}}(H) denote the connected tree-depth of HH, let χ(GHodd)\chi_{\star}(\mathcal{G}_H^{\text{odd}}) be the clustered chromatic number, and let χΔ(GHodd)\chi_{\Delta}(\mathcal{G}_H^{\text{odd}}) be the defective chromatic number. Odd-minor clustered and defective colouring conjecture. For every graph HH,

χ(GHodd)2td(H)2\chi_{\star}(\mathcal{G}_H^{\text{odd}})\leqslant 2\operatorname{\overline{td}}(H)-2

and

χΔ(GHodd)=td(H)1.\chi_{\Delta}(\mathcal{G}_H^{\text{odd}})=\operatorname{\overline{td}}(H)-1.

The paper proves the weaker upper bound χ(GHodd)32td(H)4\chi_{\star}(\mathcal{G}_H^{\text{odd}})\leqslant 3\cdot 2^{\operatorname{\overline{td}}(H)}-4 and places the conjecture as the proposed improvement; its status is not resolved in the source.

Sources & referencesView supporting material

Primary source

Robert Hickingbotham, Dong Yeap Kang, Sang-il Oum, Raphael Steiner and David R. Wood, “Clustered Colouring of Odd-H-Minor-Free Graphs”, arXiv:2308.15721 (2024).

Additional references

3 papers in this index state this conjecture (2017–2023). The statement above is taken from the most recent of them; the others are arXiv:1803.07694, arXiv:1708.02370.

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.