{"id":"arxiv/2602.02876","url":"https://arxiv.org/abs/2602.02876","tags":["math.CO"],"score":0,"title":"Frugal coloring of graphs revisited","domain":"math.CO","source":"arxiv","authors":["Boštjan Brešar","Wenjie Hu","Babak Samadi"],"reviews":0,"subject":"math.CO","summary":"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 $α_t^f(G)$, while the minimum cardinality of a $t$-frugal coloring of $G$, $χ_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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-02","reactions":{}}