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


    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

    Consultation statistics

    This page has been seen 1198 times.
    This article's PDF has been downloaded 256 times.