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

Abstract

For a graph $G$ and a tree-decomposition $(T,\mathcal{B})$ of $G$, the chromatic number of $(T,\mathcal{B})$ is the maximum of $\chi (G[B])$, taken over all bags $B\in \mathcal{B}$. The tree-chromatic number of $G$ is the minimum chromatic number of all tree-decompositions $(T,\mathcal{B})$ of $G$. The path-chromatic number of $G$ is defined analogously. In this paper, 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.

11 pages, 0 figures

Cited by in corpus (1)

• Separating Tree-chromatic number from Path-chromatic Number