Odd-minor clustered and defective colouring conjecture

About 9 years old · traced to

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)⩽3⋅2td‾⁡(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.

References

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.