论文标题
关于树和路径颜色编号的注释
Notes on Tree- and Path-chromatic Number
论文作者
论文摘要
Tree-Chromation数字是树宽的色版本，其中树状分解中的袋子的成本由其色数而不是其大小来衡量。路径染色数类似地定义。这些参数由Seymour引入（JCTB 2016）。在本文中，我们对树木和路径染色数的所有已知结果进行了调查，然后提出一些新的结果和猜想。特别是，我们提出了Hadwiger对树木数字的猜想的版本。作为证据表明我们的猜想可能比Hadwiger的猜想更容易处理，我们提供了一个简短的证据，证明每$ k_5 $ - 最少的图形最多都有$ 4 $，这避免了四种颜色定理。我们还提出了一些硬度结果和计算树木和路径颜色数的猜想。
Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic number is defined analogously. These parameters were introduced by Seymour (JCTB 2016). In this paper, we survey all the known results on tree- and path-chromatic number and then present some new results and conjectures. In particular, we propose a version of Hadwiger's Conjecture for tree-chromatic number. As evidence that our conjecture may be more tractable than Hadwiger's Conjecture, we give a short proof that every $K_5$-minor-free graph has tree-chromatic number at most $4$, which avoids the Four Colour Theorem. We also present some hardness results and conjectures for computing tree- and path-chromatic number.
