|
|||||
|
|
Injective colorings of planar graphs with few colors |
|
| Authors: | Borut Lu?ar,Riste &Scaron krekovski |
| Affiliation: | a Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia b Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia c Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranske namesti 25, 118 00 Prague, Czech Republic |
| 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 Injective coloring Injective chromatic number Discharging method |
| 本文献已被 ScienceDirect 等数据库收录！ | |