کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648815 1632433 2011 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
List injective colorings of planar graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
List injective colorings of planar graphs
چکیده انگلیسی

A vertex coloring of a graph GG is called injective if any two vertices joined by a path of length two get different colors. A graph GG is injectively kk-choosable if any list LL of admissible colors on V(G)V(G) of size kk allows an injective coloring φφ such that φ(v)∈L(v)φ(v)∈L(v) whenever v∈V(G)v∈V(G). The least kk for which GG is injectively kk-choosable is denoted by χil(G).Note that χil≥Δ for every graph with maximum degree ΔΔ. For planar graphs with girth gg, Bu et al. (2009) [15] proved that χil=Δ if Δ≥71Δ≥71 and g≥7g≥7, which we strengthen here to Δ≥16Δ≥16. On the other hand, there exist planar graphs with g=6g=6 and χil=Δ+1 for any Δ≥2Δ≥2. Cranston et al. (submitted for publication) [16] proved that χil≤Δ+1 if g≥9g≥9 and Δ≥4Δ≥4. We prove that each planar graph with g≥6g≥6 and Δ≥24Δ≥24 has χil≤Δ+1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issues 2–3, 6 February 2011, Pages 154–165
نویسندگان
, ,