Packing chromatic number of unitary Cayley graphs of \Bbb Z_n and algorithmic approaches to it

2025/05/09 by Hamed-Labbafian, Zahra, Tavakoli, Mostafa, Afkhami, Mojgan +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2505.06099

Abstract

A packing k-coloring of a graph G is a partition of V(G) into k disjoint non-empty classes V₁, …, V_k, such that if u,v ∈ V_i, i∈ [k], u≠ v, then the distance between u and v is greater than i. The packing chromatic number of G is the smallest integer k which admits a packing k-coloring of G. In this paper, the packing chromatic number of the unitary Cayley graph of ℤ_n is computed. Two metaheuristic algorithms for calculating the packing chromatic number are also proposed.

Citations

• S-packing chromatic critical graphs
• Grundy Packing Coloring of Graphs
• S-packing colorings of distance graphs with distance sets of cardinality 2
• The unitary Cayley graph of a semiring
• Packing (1,1,2,4)-coloring of subcubic outerplanar graphs
• S-packing chromatic vertex-critical graphs
• Packing (1,1,2,2)-coloring of some subcubic graphs
• Domination Parameters of the Unitary Cayley Graph of ℤ/nℤ

Related

• The packing chromatic number of the square lattice is at least 12
• Packing Chromatic Number of Distance Graphs
• Packing chromatic number under local changes in a graph
• Packing chromatic number of subcubic graphs
• Packing chromatic number of subdivisions of cubic graphs