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 等数据库收录！ |
|
