Discrete Mathematics & Theoretical Computer Science |

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

Source: arXiv.org:1806.01064

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

This page has been seen 1137 times.

This article's PDF has been downloaded 206 times.