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


Injective Colorings of Graphs with Low Average Degree
Authors:Daniel W Cranston  Seog-Jin Kim  Gexin Yu
Affiliation:1.Department of Mathematics & Applied Mathematics,Virginia Commonwealth University,Richmond,USA;2.DIMACS,Rutgers University,Piscataway,USA;3.Konkuk University,Seoul,Korea;4.College of William and Mary,Williamsburg,USA
Abstract:Let mad (G) denote the maximum average degree (over all subgraphs) of G and let χ i (G) denote the injective chromatic number of G. We prove that if Δ≥4 and mad(G) < \frac145\mathrm{mad}(G)<\frac{14}{5}, then χ i (G)≤Δ+2. When Δ=3, we show that mad(G) < \frac3613\mathrm{mad}(G)<\frac{36}{13} implies χ i (G)≤5. In contrast, we give a graph G with Δ=3, mad(G)=\frac3613\mathrm{mad}(G)=\frac{36}{13}, and χ i (G)=6.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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