Tony Huynh

Université Libre de Bruxelles

Tree-chromatic number is not equal to path-chromatic number

For a graph G and a tree-decomposition (T,B) of G, the chromatic number of (T,B) is the maximum chromatic number of all bags of (T,B). The tree-chromatic number of G is the minimum chromatic number of all tree-decompositions (T,B) of G. The path-chromatic number of G is defined analogously. 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. Our results also imply that the path-chromatic numbers of the Mycielski graphs are unbounded. This is joint work with Ringi Kim (Princeton).