Frugal coloring of graphs revisited

Abstract

Given a graph $G$ and a positive integer $t$, an independent set $S\subseteq V(G)$ is $t$-frugal if every vertex has at most $t$ neighbors in $S$. A $t$-frugal coloring of $G$ is a partition of its vertex set into $t$-frugal independent sets. The maximum cardinality of a $t$-frugal independent set in $G$ is denoted by ${\alpha }_t^f(G)$, while the minimum cardinality of a $t$-frugal coloring of $G$, ${\chi }_t^f(G)$, is called the $t$-frugal chromatic number of $G$. Frugal colorings were introduced in 1998 and studied later in just a handful of papers. In this paper, we revisit this concept. While the NP-hardness of frugal coloring is known, we prove that the decision version of ${\alpha }_t^f$ is NP-complete even for bipartite graphs, and present a linear-time algorithm to determine its value for trees. We prove a general sharp lower bound on ${\chi }_t^f(G)$ expressed in terms of ${\alpha }_t^f(G)$ and size of $G$. We also give a sharp upper bound on the ${\alpha }_2^f$ of any graph $G$, which in the case of graphs with minimum degree $\delta \ge 2$ simplifies to ${\alpha }_2^f(G)\le 2n/(\delta +2)$. We prove that $3\le {\chi }_2^f(G)\le 5$ holds for any graph $G$ with $\Delta (G)=3$. For several classes of graphs such as block graphs, the Cartesian and strong products of multiple two-way infinite paths, we determine the exact values of ${\alpha }_2^f$. We provide sharp bounds on the ${\alpha }_2^f$ in all four standard graph products, which are expressed as different invariants of their factors. Finally, we obtain Nordhaus-Gaddum type inequalities for the sum of the $2$-frugal chromatic numbers of $G$ and its complement from below and from above by functions of the order of $G$. For the upper bound ${\chi }_2^f(G)+{\chi }_2^f(\overline{G})\le 3n/2$, we characterize the family of extremal graphs $G$.