|Monday, November 30th, 2015||4pm-5pm||Burnside 1205|
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).