کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418403 681664 2012 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reconfiguration of list edge-colorings in a graph
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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 only one edge color assignment 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. We then 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 nn vertices using O(n2)O(n2) 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 Ω(n2)Ω(n2) recolor steps.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2199–2207
نویسندگان
, , ,