Authors:
A. Dong, X. Zhang
Title:
Equitable coloring and equitable choosability of graphs with small maximum average degree
Source:
Discussiones Mathematicae Graph Theory
Received 10.10.2016, Revised 16.02.2017, Accepted 16.02.2017, doi: 10.7151/dmgt.2049

Abstract:
A graph is said to be equitably k-colorable if the vertex set V(G) can be partitioned into k independent subsets V1,V2,...,Vk such that ||Vi|-|Vj||≤ 1 (1≤ i, j≤ k). A graph G is equitably k-choosable if, for any given k-uniform list assignment L, G is L-colorable and each color appears on at most \left⌈\frac{|V(G)|}{k}\right⌉ vertices. In this paper, we prove that if G is a graph such that mad(G)<3, then G is equitably k-colorable and equitably k-choosable where k≥\max{Δ(G), 4}. Moreover, if G is a graph such that mad(G)<\frac{12}{5}, then G is equitably k-colorable and equitably k-choosable where k≥\max{Δ(G), 3}.
Keywords:
graph coloring, equitable choosability, maximum average degree

Links:
PDF