کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419741 | 683856 | 2009 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Injective coloring of planar graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A coloring of a graph GG is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic number χi(G)χi(G) of a graph GG is the least kk such that there is an injective kk-coloring. In this paper we prove that if GG is a planar graph with girth gg and maximum degree ΔΔ, then (1) χi(G)=Δχi(G)=Δ if either g≥20g≥20 and Δ≥3Δ≥3, or g≥7g≥7 and Δ≥71Δ≥71; (2) χi(G)≤Δ+1χi(G)≤Δ+1 if g≥11g≥11; (3) χi(G)≤Δ+2χi(G)≤Δ+2 if g≥8g≥8.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 4, 28 February 2009, Pages 663–672
Journal: Discrete Applied Mathematics - Volume 157, Issue 4, 28 February 2009, Pages 663–672
نویسندگان
Yuehua Bu, Dong Chen, André Raspaud, Weifan Wang,