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

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
نویسندگان
, , , ,