Equitable Coloring of Degenerate Graphs
Junlei Zhu · Journal of Jiaxing University · 2010
A graph G is equitably k-colorable,if G has a proper k-vertex coloring that the sizes of any two color classes differ by at most 1. χe(G) = min{k |G is equitably k-colorable} is called the equitable chromatic number of G . A graph G is called d-degenerate if every included subgraph H of G contains a vertex of degree at most d . In this paper,we prove that d-degenerate graphs G with |E(G)|≤2/3 |V(G)| is equitably 3-colorable where d = 1,2 and d-degenerate graphs G with |E(G)|≤3/4|V(G)| is equitably 4-colorable where d= 2,3.