Article ID Journal Published Year Pages File Type
4649460 Discrete Mathematics 2009 14 Pages PDF
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Δ+1)-colorable, that Δ+4Δ+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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,