S-packing colorings of distance graphs with distance sets of cardinality 2

Boštjan Brešar, Jasmina Ferme, Přemysl Holub, Marko Jakovac and Petra Melicharová

Applied Mathematics and Computation, 2025, vol. 490, issue C

Abstract: 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. In this paper, we consider S-packing colorings of the integer distance graphs with respect two positive integers k and t, which are the graphs whose vertex set is Z, and two vertices x,y∈Z are adjacent whenever |x−y|∈{k,t}. We complement partial results from two earlier papers, thus determining all values of the S-packing chromatic numbers of these distance graphs for all sequence S such that 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.

Keywords: S-packing coloring; S-packing chromatic number; Distance graph; Distance coloring (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324006611
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:490:y:2025:i:c:s0096300324006611

DOI: 10.1016/j.amc.2024.129200

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().