Packing coloring of graphs with long paths
Preprint
Abstract
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.~\cite{goddard2008broadcast} showed that the packing chromatic numbers of paths and cycles are at most 3 and 4, respectively. In this paper, we introduce \emph{path-aligned graph products}, a natural extension of paths with unbounded diameter. We extend the result of~\cite{goddard2008broadcast} 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~\cite{sloper} 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.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Charging strategies and battery ageing for electric vehicles: A reviewEnergy Strategy Reviews, 2025
- A survey on packing coloringsDiscussiones Mathematicae Graph Theory, 2020
- Packing coloring of some undirected and oriented coronae graphsDiscussiones Mathematicae Graph Theory, 2017
- Modeling the packing coloring problem of graphsApplied Mathematical Modelling, 2015
- Complexity of the packing coloring problem for treesDiscrete Applied Mathematics, 2010
- On the packing chromatic number of Cartesian products, hexagonal lattice, and treesDiscrete Applied Mathematics, 2007