2025/11/16 by Hanna Furmańczyk, Furmańczyk, Hanna, Didem Gözüpek +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2511.12761
openalex publication_date 2025/11/16 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28
The packing coloring problem has diverse applications, including frequency assignment in wireless networks, resource distribution and facility location in smart cities and post-disaster management, as well as in biological diversity. Formally, the packing coloring of a graph is a vertex coloring in which any two vertices assigned color i are at a distance of at least i+1, and the smallest number of colors admitting such a coloring is called the packing chromatic number. Goddard et al.~\citegoddard2008broadcast showed that the packing chromatic numbers of paths and cycles are at most 3 and 4, respectively. In this paper, we introduce path-aligned graph products, a natural extension of paths with unbounded diameter. We extend the result of~\citegoddard2008broadcast by proving that the packing chromatic number remains bounded by a constant for several families of path-aligned cycle and path-aligned complete products. We then investigate the packing chromatic number of caterpillars, another class of graphs characterized by long induced paths. Sloper~\citesloper proved that the packing chromatic number of caterpillars is at most 7; here, we provide a complete structural characterization of caterpillars with packing chromatic number at most 3. Finally, several open research questions are posed.