Limits of Near‐Coloring of Sparse Graphs
Limits of Near‐Coloring of Sparse Graphs
复制标题
DOI：
10.1002/jgt.21731
复制
发表时间：
2012-10
影响因子：
0.9
通讯作者：
Paul Dorbec;Tomás Kaiser;Mickaël Montassier;A. Raspaud
中科院分区：
文献类型：
--
作者：
Paul Dorbec;Tomás Kaiser;Mickaël Montassier;A. Raspaud
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 1≤i≤a , while the graph G[Oj] induced by Oj 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 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).
