Aijun Dong ; Jianliang Wu - 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-CyclesArticle

Authors: Aijun Dong ; Jianliang Wu

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\}$.

Comment: 21 pages,3 figures


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

1 Document citing this article

Consultation statistics

This page has been seen 1462 times.
This article's PDF has been downloaded 456 times.