کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418653 681703 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Chromatic-choosability of the power of graphs
ترجمه فارسی عنوان
اختیاری کروماتیک قدرت گراف ها
کلمات کلیدی
فهرست رنگ آمیزی، انتخاب رنگی، قدرت گراف ها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The kkth power GkGk of a graph GG is the graph defined on V(G)V(G) such that two vertices uu and vv are adjacent in GkGk if the distance between uu and vv in GG is at most kk. Let χ(H)χ(H) and χℓ(H)χℓ(H) be the chromatic number and the list chromatic number of HH, respectively. A graph HH is called chromatic-choosable   if χℓ(H)=χ(H)χℓ(H)=χ(H). It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2013) is whether there exists a constant integer kk such that GkGk is chromatic-choosable for every graph GG.Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether G2G2 is chromatic-choosable for every graph GG. Kim and Park (2014) solved Kostochka and Woodall’s conjecture in the negative by finding a family of graphs G whose squares are complete multipartite graphs with partite sets of unbounded size. In this paper, we answer Zhu’s question by showing that for every integer k≥2k≥2, there exists a graph GG such that GkGk is not chromatic-choosable. Moreover, for any fixed kk we show that the value χℓ(Gk)−χ(Gk)χℓ(Gk)−χ(Gk) can be arbitrarily large.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 180, 10 January 2015, Pages 120–125
نویسندگان
, , ,