Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions |
| |
| Authors: | Jaehoon Kim Alexandr Kostochka Xuding Zhu |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF ILLINOIS, URBANA, IL;2. SCHOOL OF MATHEMATICS UNIVERSITY OF BIRMINGHAM, EDGBASTON, BIRMINGHAM, UK;3. ZHEJIANG NORMAL UNIVERSITY, JINHUA, CHINA |
| |
| Abstract: | A graph G is  ‐colorable if  can be partitioned into two sets  and  so that the maximum degree of  is at most j and of  is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with  in place of (0, 0) is NP‐complete for all nonnegative j and k with  . Let  denote the supremum of all x such that for some constant  every graph G with girth g and  for every  is  ‐colorable. It was proved recently that  . In a companion paper, we find the exact value  . In this article, we show that increasing g from 5 further on does not increase  much. Our constructions show that for every g,  . We also find exact values of  for all g and all  . |
| |
| Keywords: | improper coloring defective coloring sparse graph girth |
|
|
