کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426754 686259 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Closing complexity gaps for coloring problems on H-free graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Closing complexity gaps for coloring problems on H-free graphs
چکیده انگلیسی

If a graph G contains no subgraph isomorphic to some graph H, then G is called H  -free. A coloring of a graph G=(V,E)G=(V,E) is a mapping c:V→{1,2,…}c:V→{1,2,…} such that no two adjacent vertices have the same color, i.e., c(u)≠c(v)c(u)≠c(v) if uv∈Euv∈E; if |c(V)|⩽k|c(V)|⩽k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u   receives a color from some given set L(u)L(u). By imposing an upper bound ℓ   on the size of each L(u)L(u) we obtain the ℓ-List Coloring problem. We first classify the Precoloring Extension problem and the ℓ-List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n  -vertex graphs of minimum degree n−2n−2, i.e., for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n−2n−2. Finally, for a fixed integer k>0k>0, the Listk-Coloring problem is to decide whether a graph allows a coloring, such that every vertex u   receives a color from some given set L(u)L(u) that must be a subset of {1,…,k}{1,…,k}. We show that List 4-Coloring is NP-complete for P6P6-free graphs, where P6P6 is the path on six vertices. This completes the classification of Listk-Coloring for P6P6-free graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 237, October 2014, Pages 204–214
نویسندگان
, , ,