Partitioning an $S$-packing coloring into broadcast dominating sets

Source abstract

Given a graph $G$ and a positive integer $k$, a packing $k$-domatic coloring of $G$ is a function $f: V(G) \to \{1,\ldots,t\}$ such that (1) for any color $j \in \{1,\ldots, t\}$ and any two distinct vertices $u,v\in V(G)$ with $f(u)=f(v)=j$ we have $d_G(u,v)>j$, and (2) $V(G)$ admits a partition into $k$ sets $A_1,\ldots,A_k$ such that for any $v\in V(G)$ and any $i\in\{1,\ldots,k\}$ there exists a vertex $w\in A_i$ such that $d_G(v,w)\le f(w)$. The minimum integer $t$ such that $G$ admits a packing $k$-domatic coloring of $G$ using colors in $\{1,\ldots,t\}$ is denoted by $χ_{ρ,k}(G)$. The condition (1) in the definition of a packing $k$-domatic coloring implies that $G$ is a packing coloring, hence $χ_{ρ,k}(G)\ge χ_ρ(G)$ holds for any graph $G$, where $χ_ρ(G)$ is the packing chromatic number of $G$. On the other hand, the new concept also leads to a generalization of the domatic number of a graph due to which one can easily see that $χ_{ρ,2}(G)=χ_ρ(G)$ holds for any graph with no isolated vertices. One of the main result in this paper is that $χ_{ρ,3}(G)=χ_ρ(G)$ holds in any connected graph $G$ with minimum degree at least $2$, and the bound is best possible in two different senses. In addition, we provide several exact values and bounds on the new invariant in paths and cycles. We prove that $χ_{ρ,k}(P_n)=k$ for any $k\in\{3,4,5\}$ as soon as $n\ge 8$, and, in contrast, $χ_{ρ,k}(P_n)>k$ for any $n\ge k\ge 12$. We also prove the exact values of $χ_{ρ,k}(P_\infty)$ when $k\in \{3,4,5\}$ for the two-way infinite path $P_\infty$, and exact values of $χ_{ρ,k}(C_n)$ when $k\in\{3,4\}$ for all cycles $C_n$. We also consider a general framework of $S$-packing $k$-domatic colorings, where $S$ is an arbitrary sequence of non-negative integers, and present some basic results in this context.