Title of article :
Injective colorings of planar graphs with few colors
Author/Authors :
Lu?ar، نويسنده , , Borut and ?krekovski، نويسنده , , Riste and Tancer، نويسنده , , Martin، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
14
From page :
5636
To page :
5649
Abstract :
An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ -colorable. We also show that all planar graphs of girth ≥ 10 are injectively ( Δ + 1 )-colorable, that Δ + 4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.
Keywords :
graph coloring , discharging method , Injective chromatic number , Injective coloring
Journal title :
Discrete Mathematics
Serial Year :
2009
Journal title :
Discrete Mathematics
Record number :
1599100
Link To Document :
بازگشت