Partitioning an S-packing coloring into broadcast dominating sets
Abstract
Given a graph G and a positive integer k, a packing k-domatic coloring of G is a function f: V(G) → {1,…,t} such that (1) for any color j ∈ {1,…, t} and any two distinct vertices u,v∈ V(G) with f(u)=f(v)=j we have dG(u,v)>j, and (2) V(G) admits a partition into k sets A1,…,Ak such that for any v∈ V(G) and any i∈{1,…,k} there exists a vertex w∈ Ai such that dG(v,w)≤ f(w). The minimum integer t such that G admits a packing k-domatic coloring of G using colors in {1,…,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)≥ χρ(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(Pn)=k for any k∈{3,4,5} as soon as n≥ 8, and, in contrast, χρ,k(Pn)>k for any n≥ k≥ 12. We also prove the exact values of χρ,k(P∞) when k∈ {3,4,5} for the two-way infinite path P∞, and exact values of χρ,k(Cn) when k∈{3,4} for all cycles Cn. 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.
Related
- Non-asymptotic Sphere-Packing Bounds for Finite-Blocklength Scalar Gaussian Multiple-Access and Broadcast Channels
- A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set
- Notes on efficient dominating sets and efficient open dominating sets in circulant graphs
- Every cubic graph has four total dominating sets covering each vertex at most twice
- Prime Nullspace Matrices and Even Dominating Sets
BibTeX
@misc{bresar2026partitioning,
title = {{Partitioning an $S$-packing coloring into broadcast dominating sets}},
author = {Boštjan Brešar and Jasmina Ferme and Wenjie Hu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03477},
eprint = {2610.03477},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03477},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Partitioning an S-packing coloring into broadcast dominating sets
AU - Boštjan Brešar
AU - Jasmina Ferme
AU - Wenjie Hu
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03477
UR - https://arxiv.org/abs/2610.03477
AB - Given a graph G and a positive integer k, a packing k-domatic coloring of G is a function f: V(G) → {1,…,t} such that (1) for any color j ∈ {1,…, t} and any two distinct vertices u,v∈ 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,…,A_k such that for any v∈ V(G) and any i∈{1,…,k} there exists a vertex w∈ A_i such that d_G(v,w)≤ f(w). The minimum integer t such that G admits a packing k-domatic coloring of G using colors in {1,…,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)≥ χ_ρ(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∈{3,4,5} as soon as n≥ 8, and, in contrast, χ_ρ,k(P_n)>k for any n≥ k≥ 12. We also prove the exact values of χ_ρ,k(P_∞) when k∈ {3,4,5} for the two-way infinite path P_∞, and exact values of χ_ρ,k(C_n) when k∈{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.
ER -