论文标题
几乎两分图的kempe等效性
Kempe equivalence of almost bipartite graphs
论文作者
论文摘要
如果可以通过两种顶点的两种颜色的切换序列将它们相互转换，则图形的两个顶点着色是等效的。确定图形的两个给定顶点$ k $ - 色对于任何固定的$ k \ geq 3 $都等效于pspace complete，并且很容易看出，任何二倍体图的每两个顶点颜色均为kempe等效。在本文中，我们考虑了{\ it几乎}两分图的kempe等效性，可以通过添加几个边来连接同一党集中的两个顶点，从而从两部分图获得。我们给出了这种图形的kempe等效性的猜想，我们证明了几种部分解决方案和最佳可能性，但是Cranston和Feghali最近证明了这一猜想通常是错误的。
Two vertex colorings of a graph are Kempe equivalent if they can be transformed into each other by a sequence of switchings of two colors of vertices. It is PSPACE-complete to determine whether two given vertex $k$-colorings of a graph are Kempe equivalent for any fixed $k\geq 3$, and it is easy to see that every two vertex colorings of any bipartite graph are Kempe equivalent. In this paper, we consider Kempe equivalence of {\it almost} bipartite graphs which can be obtained from a bipartite graph by adding several edges to connect two vertices in the same partite set. We give a conjecture of Kempe equivalence of such graphs, and we prove several partial solutions and best possibility of the conjecture, but it is more lately proved by Cranston and Feghali that this conjecture is false in general.
