Limits of Near‐Coloring of Sparse Graphs |
| |
| Authors: | Paul Dorbec Tomáš Kaiser Mickael Montassier André Raspaud |
| |
| Affiliation: | 1. UNIVERSITY OF BORDEAUX, LABRI UMR5800, F‐33400 TALENCE, FRANCE;2. CNRS, LaBRI UMR5800, F‐33400 TALENCE, FRANCE;3. DEPARTMENT OF MATHEMATICS AND INSTITUTE FOR THEORETICAL COMPUTER SCIENCE (ITI), UNIVERSITY OF WEST BOHEMIA UNIVERZITNí 8, CZECH REPUBLIC |
| |
| Abstract: | Let  be nonnegative integers. A graph G is  ‐colorable if its vertex set can be partitioned into  sets  such that the graph  induced by  has maximum degree at most d for  , while the graph  induced by  is an edgeless graph for  . In this article, we give two real‐valued functions  and  such that any graph with maximum average degree at most  is  ‐colorable, and there exist non‐ ‐colorable graphs with average degree at most  . Both these functions converge (from below) to  when d tends to infinity. This implies that allowing a color to be d‐improper (i.e., of type  ) 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  (even with a very large degree d) is somehow less powerful than using two colors of type  (two stable sets). |
| |
| Keywords: | colorings improper colorings maximum average degree |
|
|
