کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647912 1342382 2012 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Injective choosability of planar graphs of girth five and six
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Injective choosability of planar graphs of girth five and six
چکیده انگلیسی

An injective k-coloring   of a graph GG is an assignment of kk colors to V(G)V(G) such that vertices having a common neighbor receive distinct colors. We study the list version of injective colorings of planar graphs. Let χil(G) and mad(G)mad(G) be the injective choosability number and the maximum average degree of GG, respectively. It is proved that (1) for each graph GG with mad(G)<103, χil(G)≤Δ(G)+4 if Δ(G)≥30Δ(G)≥30 (this conditionally improves some results of Doyon et al. (2010) [9] and Lužar et al. (2009) [11]), χil(G)≤Δ(G)+5 if Δ(G)≥18Δ(G)≥18, and χil(G)≤Δ(G)+6 if Δ(G)≥14Δ(G)≥14; (2) χil(G)≤Δ(G)+2 if mad(G)<3mad(G)<3 and Δ(G)≥12Δ(G)≥12 (this conditionally improves a result of Doyon et al. (2010) [9]).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 6, 28 March 2012, Pages 1260–1265
نویسندگان
, ,