Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number* |
| |
| Authors: | Tony Huynh Ringi Kim |
| |
| Institution: | 1. DEPARTMENT OF MATHEMATICS, UNIVERSITé LIBRE DE BRUXELLES, BOULEVARD DU TRIOMPHE, B-1050, BRUSSELS, BELGIUM;2. DEPARTMENT OF COMBINATORICS AND OPTIMIZATION, UNIVERSITY OF WATERLOO, WATERLOO, ONTARIO, CANADA |
| |
| 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. |
| |
| Keywords: | tree‐decompositions path‐decompositions chromatic number Mycielski graphs |
|
|
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.