Scholarlink

The clustered chromatic number of a graph class \(\mathcal{g}\) is the minimum integer c such that every graph \(G\in \mathcal{g}\) has a c-colouring where each monochromatic component in G has bounded size. We study the clustered chromatic number of graph classes \({\mathcal{g}}_{H}^{\text{odd}}\) defined by excluding a graphHas an odd-minor. How does the structure ofHrelate to the clustered chromatic number of \({\mathcal{g}}_{H}^{\text{odd}}\) ? We adapt a proof method of Norin, Scott, Seymour and Wood (2019) to show that the clustered chromatic number of \({\mathcal{g}}_{H}^{\text{odd}}\) is tied to the tree-depth of H.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Clustered Colouring of Odd-H-Minor-Free Graphs

  • 章节

  • 发表日期：

    2025年

查看全文
  • Robert Hickingbotham,
  • Dong Yeap Kang,
  • Sang-il Oum,
  • Raphael Steiner,
  • David R. Wood

摘要

The clustered chromatic number of a graph class \(\mathcal{g}\) is the minimum integer c such that every graph \(G\in \mathcal{g}\) has a c-colouring where each monochromatic component in G has bounded size. We study the clustered chromatic number of graph classes \({\mathcal{g}}_{H}^{\text{odd}}\) defined by excluding a graphHas an odd-minor. How does the structure ofHrelate to the clustered chromatic number of \({\mathcal{g}}_{H}^{\text{odd}}\) ? We adapt a proof method of Norin, Scott, Seymour and Wood (2019) to show that the clustered chromatic number of \({\mathcal{g}}_{H}^{\text{odd}}\) is tied to the tree-depth of H.