Anzeige
Erschienen in:
2021 | OriginalPaper | Buchkapitel
Notes on Tree- and Path-Chromatic Number
verfasst von : Tony Huynh, Bruce Reed, David R. Wood, Liana Yepremyan
Erschienen in: 2019-20 MATRIX Annals
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic number is defined analogously. These parameters were introduced by Seymour [JCTB 2016]. In this paper, we survey all the known results on tree- and path-chromatic number and then present some new results and conjectures. In particular, we propose a version of Hadwiger’s Conjecture for tree chromatic number. As evidence that our conjecture may be more tractable than Hadwiger’s Conjecture, we give a short proof that every K5-minor-free graph has tree-chromatic number at most 4, which avoids the Four Colour Theorem. We also present some hardness results and conjectures for computing tree- and path chromatic number.