Injective coloring of planar graphs |
| |
Authors: | Yuehua Bu André Raspaud |
| |
Institution: | a Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China b LaBRI UMR CNRS 5800, Université Bordeaux I, 33405 Talence Cedex, France |
| |
Abstract: | A coloring of a graph G is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic numberχi(G) of a graph G is the least k such that there is an injective k-coloring. In this paper we prove that if G is a planar graph with girth g and maximum degree Δ, then (1) χi(G)=Δ if either g≥20 and Δ≥3, or g≥7 and Δ≥71; (2) χi(G)≤Δ+1 if g≥11; (3) χi(G)≤Δ+2 if g≥8. |
| |
Keywords: | Planar graph Injective chromatic number Girth |
本文献已被 ScienceDirect 等数据库收录! |
|