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 V_{1},V_{2},...,V_{k} such that ||V_{i}|-|V_{j}||≤ 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: |