Dong, Aijun and Wu, Jianliang - Equitable Coloring and Equitable Choosability of Planar Graphs without chordal 4- and 6-Cycles

dmtcs:4566 - Discrete Mathematics & Theoretical Computer Science, November 11, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-16
Equitable Coloring and Equitable Choosability of Planar Graphs without chordal 4- and 6-Cycles

Authors: Dong, Aijun and Wu, Jianliang

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||\leq 1$ for $1\leq i, j\leq 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\geq\max\{\Delta(G), 7\}$.


Volume: Vol. 21 no. 3
Section: Graph Theory
Published on: November 11, 2019
Submitted on: June 5, 2018
Keywords: Mathematics - Combinatorics,05C15


Share

Consultation statistics

This page has been seen 723 times.
This article's PDF has been downloaded 34 times.