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

2015/05/22 by Huynh, Tony, Kim, Ringi · 4 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1505.06234

Abstract

For a graph G and a tree-decomposition (T, B) of G, the chromatic number of (T, B) is the maximum of χ(G[B]), taken over all bags B ∈ 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. 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.

Cited by

• Optimal Tree-Decompositions with Bags of Bounded Treewidth
• Awesome graph parameters
• Optimal tree-decompositions with bags of bounded pathwidth
• Tree decompositions with small width, spread, order and degree

Related

• Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number^*
• Notes on Tree- and Path-chromatic Number
• Separating Tree-chromatic number from Path-chromatic Number
• On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs
• Induced subgraphs of graphs with large chromatic number. IX. Rainbow paths