Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number*
Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number*
复制标题
树色数不等于路径色数*
作者：
T. Huynh;Ringi Kim
对于图 G 和 G 的树分解 (T,B)，(T,B) 的色数是 χ(G[B]) 的最大值，涵盖所有包 B∈B 。 G 的树色数是 G 的所有树分解 (T,B) 的最小色数。G 的路径色数的定义类似。在本文中，我们介绍了一种总是增加图的路径色数的操作。作为我们构造的一个简单推论，我们获得了无限族的图，其路径色数和树色数不同。这解决了 Seymour 的问题（J Combin Theory Ser B 116 (2016), 229–237）。我们的结果还表明 Mycielski 图的路径色数是无界的。
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 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.