Limits of Near‐Coloring of Sparse Graphs |
| |
Authors: | Paul Dorbec Tomá? Kaiser Mickael Montassier André Raspaud |
| |
Institution: | 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 |
|
|