Menu
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)| \geq 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) \geq \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 1 \) for any graph \( G \) with maximum degree \( \Delta(G) \). In this paper, we prove that for any integer \( k \geq 4 \), if \( G \) is a planar graph with maximum degree \( \Delta(G) \geq 13k – 11 \) and girth \( g \geq 6 \), then \( \text{ch}_k(G) = \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 1; \) and if \( G \) is a planar graph with girth \( g \geq 6 \), then \(\text{ch}_k(G) \leq \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 2.\)