Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number*
Tony Huynh, Ringi Kim · Journal of Graph Theory · 2017
Abstract For a graph G and a tree‐decomposition of G, the chromatic number of is the maximum of , taken over all bags . The tree‐chromatic number of G is the minimum chromatic number of all tree‐decompositions of G. The path‐chromatic number of G is defined analogously. In this article, we introduce an operation that always increases the path‐chromatic number of a graph. As an easy corollary of our construction, we obtain an infinite family of graphs whose path‐chromatic number and tree‐chromatic number are different. This settles a question of Seymour (J Combin Theory Ser B 116 (2016), 229–237). Our results also imply that the path‐chromatic numbers of the Mycielski graphs are unbounded.