Injective colorings of sparse graphs |
| |
| Authors: | Daniel W Cranston Seog-Jin Kim |
| |
| Institution: | a Virginia Commonwealth University, Richmond, VA, United Statesb DIMACS, Rutgers University, Piscataway, NJ, United Statesc Konkuk University, Seoul, Republic of Koread College of William and Mary, Willliamsburg, VA 23185, United States |
| |
| Abstract: | Let  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  , then χi(G)≤Δ(G)+1; and if  , then χi(G)=Δ(G). Suppose that G is a planar graph with girth g(G) and Δ(G)≥4. We prove that if g(G)≥9, then χi(G)≤Δ(G)+1; similarly, if g(G)≥13, then χi(G)=Δ(G). |
| |
| Keywords: | Injective coloring Maximum average degree Planar graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
