کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650850 1342506 2007 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Choosability of graphs with infinite sets of forbidden differences
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Choosability of graphs with infinite sets of forbidden differences
چکیده انگلیسی

The notion of the list-T-coloring is a common generalization of the T-coloring and the list-coloring. Given a set of non-negative integers T, a graph G and a list-assignment L, the graph G is said to be T-colorable from the list-assignment L if there exists a coloring c   such that the color c(v)c(v) of each vertex vv is contained in its list L(v)L(v) and |c(u)-c(v)|∉T|c(u)-c(v)|∉T for any two adjacent vertices u   and vv. The T-choice number of a graph G is the minimum integer k such that G is T-colorable for any list-assignment L which assigns each vertex of G a list of at least k colors.We focus on list-T-colorings with infinite sets T. In particular, we show that for any fixed set T of integers, all graphs have finite T-choice number if and only if the T  -choice number of K2K2 is finite. For the case when the T  -choice number of K2K2 is finite, two upper bounds on the T-choice number of a graph G are provided: one being polynomial in the maximum degree of the graph G, and the other being polynomial in the T  -choice number of K2K2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 23, 6 November 2007, Pages 3040–3047
نویسندگان
,