Limits of Near‐Coloring of Sparse Graphs

Let a , b , d be nonnegative integers. A graph G is( d , a , b ) * ‐colorable if its vertex set can be partitioned into a + b setsD 1 , ... , D a , O 1 , ... , O bsuch that the graph G [ D i ] induced by D i has maximum degree at most d for 1 ≤ i ≤ a , while the graph G [ O j ] induced by O j is an edgeless graph for 1 ≤ j ≤ b . In this article, we give two real‐valued functions f and g such that any graph with maximum average degree at most f ( d , a , b ) is( d , a , b ) * ‐colorable, and there exist non‐ ( d , a , b ) * ‐colorable graphs with average degree at most g ( d , a , b ) . Both these functions converge (from below) to 2 a + b when d tends to infinity. This implies that allowing a color to be d ‐improper (i.e., of type D i ) even for a large degree d increases the maximum average degree that guarantees the existence of a valid coloring only by 1. Using a color of type D i (even with a very large degree d ) is somehow less powerful than using two colors of type O j (two stable sets).