Premium
Limits of Near‐Coloring of Sparse Graphs
Author(s) -
Dorbec Paul,
Kaiser Tomáš,
Montassier Mickael,
Raspaud André
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21731
Subject(s) - mathematics , combinatorics , degree (music) , complete coloring , fractional coloring , brooks' theorem , list coloring , graph , vertex (graph theory) , graph coloring , discrete mathematics , edge coloring , 1 planar graph , graph power , line graph , physics , acoustics
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).