Limits of Near-Coloring of Sparse Graphs

作者：Dorbec Paul^*; Kaiser Tomas; Montassier Mickael; Raspaud Andre

来源：Journal of Graph Theory, 2014, 75(2): 191-202.

DOI：10.1002/jgt.21731

• colorings
• improper colorings
• maximum average degree

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 sets D1,...,Da,O1,...,Ob such that the graph G[Di] induced by Di has maximum degree at most d for 1ia, while the graph G[Oj] induced by Oj is an edgeless graph for 1jb. 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 2a+b when d tends to infinity. This implies that allowing a color to be d-improper (i.e., of type Di) 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 Di (even with a very large degree d) is somehow less powerful than using two colors of type Oj (two stable sets).

• 出版日期2014-2