2024/05/29 by Boštjan Brešar, Brešar, Boštjan, Jasmina Ferme +7 · 2 citations
Computer Science · Engineering · #05C12 #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · doi:10.48550/arxiv.2405.18904
openalex publication_date 2024/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a non-decreasing sequence S=(s1,s2,…) of positive integers, a partition of the vertex set of a graph G into subsets X1,…, X_ℓ, such that vertices in Xi are pairwise at distance greater than si for every i∈\1,…,ℓ\, is called an S-packing ℓ-coloring of G. The minimum ℓ for which G admits an S-packing ℓ-coloring is called the S-packing chromatic number of G, denoted by χS(G). In this paper, we consider S-packing colorings of distance graphs G(ℤ,\k,t\), where k and t are positive integers, which are the graphs whose vertex set is ℤ, and two vertices x,y∈ ℤ are adjacent whenever |x-y|∈\k,t\. We complement partial results from two earlier papers, thus determining all values of χS(G(ℤ,\k,t\)) when S is any sequence with si≤ 2 for all i. In particular, if S=(1,1,2,2,…), then the S-packing chromatic number is 2 if k+t is even, and 4 otherwise, while if S=(1,2,2,…), then the S-packing chromatic number is 5, unless \k,t\=\2,3\ when it is 6; when S=(2,2,2,…), the corresponding formula is more complex.