z-logo
open-access-imgOpen Access
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}.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom