首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号