@inbook{6116838257484585a60deb53b8555aed,

title = "Notes on Tree- and Path-Chromatic Number",

abstract = "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{\textquoteright}s Conjecture for tree chromatic number. As evidence that our conjecture may be more tractable than Hadwiger{\textquoteright}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.",

author = "Tony Huynh and Reed, {Bruce A} and Wood, {David R} and Liana Yepremyan",

year = "2021",

doi = "10.1007/978-3-030-62497-2_30",

language = "English",

isbn = "9783030624965",

volume = "4",

series = "MATRIX Book Series",

publisher = "Springer",

number = "1",

pages = "489--498",

editor = "Wood, {David R} and {de Gier}, Jan and Praeger, {Cheryl E} and Terence Tao",

booktitle = "2019-20 MATRIX Annals",

edition = "1",

}