Equitable Coloring and Equitable Choosability of Planar Graphs without chordal 4- and 6-Cycles

Abstract

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 $\lceil \frac{|V(G)|}{k}\rceil$ vertices. A graph is equitably $k$-colorable if the vertex set $V(G)$ can be partitioned into $k$ independent subsets $V_1$, $V_2$, $\cdots$, $V_k$ such that $||V_i|-|V_j||\le 1$ for $1\le i,j\le k$. In this paper, we prove that if $G$ is a planar graph without chordal $4$- and $6$-cycles, then $G$ is equitably $k$-colorable and equitably $k$-choosable where $k\ge \max \{\Delta (G),7\}$.

21 pages,3 figures

Cited by in corpus (1)

• A Note on the Equitable Choosability of Complete Bipartite Graphs