Publication at Faculty of Mathematics and Physics |
2009
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 at least 19 and maximum degree \Delta are injectively \Delta-colorable. We also show that all planar graphs of girth at leas 10 are injectively (\Delta 1)-colorable, \Delta 4 colors are sufficient for planar graphs of girth at least 5 if \Delta is large enough, and that subcubic graphs of girth at least 7 are injectively 5-colorable.