Reconfiguration of List Edge-Colorings in a Graph

摘要

We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing one edge color at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. First we show that this problem is PSPACE-complete, even for planar graphs of maximum degree 3 and just six colors. Then we consider the problem restricted to trees. We show that any list edge-coloring can be transformed into any other under the sufficient condition that the number of allowed colors for each edge is strictly larger than the degrees of both its endpoints. This sufficient condition is best possible in some sense. Our proof yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices using O(n~2) recolor steps. This worst-case bound is tight: we give an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(n~2) recolor steps.%本論文では，同じグラフのリスト辺彩色が2つ与えられたとき，一方の彩色から他方の彩色へ段階的に変形可能かどうか判定する問題を扱う．ただし，1回に変更できるのは1本の辺の色のみであり，変形の途中で得られる彩色は全てリスト辺彩色でなければならない．まず．本論文では，各辺のリストが6色から選ばれている最大次数3の平面的グラフに対してさえ，この問題はPSPACE完全であることを示す．次に，問題を木に限定することで．任意のリスト辺彩色が互いに変形可能であるための十分条件を与える．具体的には，木の各辺に与えられたリストの色数がその辺のどちらの端点の次数より真に大きいとき，木の任意のリスト辺彩色は任意の他のリスト辺彩色に変形可能であることを示す．この十分条件は，ある意味で最良である．我々の証明は，O（n~2）ステップで与えられたリスト辺彩色を実際に変形する多項式時間アルゴリズムを与える．ここで，れは木の点数である．また，十分条件を満たす道でΩ（n~2）ステップの変形を必要とする問題例を与えることで，上記のバウンドがタイトであることを示す．