论文标题
树宽2的重色图2
Recoloring graphs of treewidth 2
论文作者
论文摘要
如果图完全不同，则图形的两个（适当的）着色是相邻的。 Jerrum证明了任何D-De-De-De-De-Degenate图的颜色的任何$（D + 2）$都可以通过一系列相邻的颜色转化为其他颜色。 Bonamy等人的结果。确保最短的转换即使对于$ d = 1 $也可以具有二次长度。 Bousquet和Perarnau证明了$（2D + 2）$ - 颜色之间存在线性转换。它开放以确定是否可以减少此界限。在本说明中，我们证明可以将其用于2级化的树宽2的图。 5色之间存在线性转换。它完成了TreeWidth 2图的图片，因为存在树宽2的图2，因此不存在4色之间的线性转换。
Two (proper) colorings of a graph are adjacent if they differ on exactly one vertex. Jerrum proved that any $(d + 2)$-coloring of any d-degenerate graph can be transformed into any other via a sequence of adjacent colorings. A result of Bonamy et al. ensures that a shortest transformation can have a quadratic length even for $d = 1$. Bousquet and Perarnau proved that a linear transformation exists for between $(2d + 2)$-colorings. It is open to determine if this bound can be reduced. In this note, we prove that it can be reduced for graphs of treewidth 2, which are 2-degenerate. There exists a linear transformation between 5-colorings. It completes the picture for graphs of treewidth 2 since there exist graphs of treewidth 2 such a linear transformation between 4-colorings does not exist.
