Equitable coloring and equitable choosability of graphs with small maximum average degree
Author(s) -
Aijun Dong,
Xin Zhang
Publication year - 2018
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2049
Subject(s) - mathematics , combinatorics , list coloring , degree (music) , complete coloring , edge coloring , fractional coloring , graph , physics , line graph , acoustics , graph power
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 ⌈|V(G)|k⌉ $\left\lceil {{{\left| {V(G)} \right|} \over k}} \right\rceil$ 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 125 ${{12} \over 5}$ , then G is equitably k-colorable and equitably k-choosable where k ≥ max{Δ (G), 3}.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom