$k$-Frugal List Coloring of Planar Graphs Without Small Cycles

Abstract

A graph $G$ is $k$-frugal colorable if there exists a proper vertex coloring of $G$ such that every color appears at most $k–1$ times in the neighborhood of $v$. The $k$-frugal chromatic number, denoted by ${\chi }_k(G)$, is the smallest integer $l$ such that $G$ is $k$-frugal colorable with $l$ colors. A graph $G$ is $L$-list colorable if there exists a coloring $c$ of $G$ for a given list assignment $L=\{L(v):v\in V(G)\}$ such that $c(v)\in L(v)$ for all $v\in V(G)$. If $G$ is $k$-frugal $L$-colorable for any list assignment $L$ with $|L(v)|\ge l$ for all $v\in V(G)$, then $G$ is said to be $k$-frugal $l$-list-colorable. The smallest integer $l$ such that the graph $G$ is $k$-frugal $l$-list-colorable is called the $k$-frugal list chromatic number, denoted by ${\text{ch}}_k(G)$. It is clear that ${\text{ch}}_k(G)\ge \lceil \frac{\mathrm{\Delta }(G)}{k–1}\rceil +1$ for any graph $G$ with maximum degree $\mathrm{\Delta }(G)$. In this paper, we prove that for any integer $k\ge 4$, if $G$ is a planar graph with maximum degree $\mathrm{\Delta }(G)\ge 13k–11$ and girth $g\ge 6$, then ${\text{ch}}_k(G)=\lceil \frac{\mathrm{\Delta }(G)}{k–1}\rceil +1;$ and if $G$ is a planar graph with girth $g\ge 6$, then ${\text{ch}}_k(G)\le \lceil \frac{\mathrm{\Delta }(G)}{k–1}\rceil +2.$