2020/05/21 by Boštjan Brešar, Brešar, Boštjan, Jasmina Ferme +3
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2005.10491
Given a graph G and a non-decreasing sequence S=(a1,a2,…) of positive integers, the mapping f:V(G) → \1,…,k\ is an S-packing k-coloring of G if for any distinct vertices u,v∈ V(G) with f(u)=f(v)=i the distance between u and v in G is greater than ai. The smallest k such that G has an S-packing k-coloring is the S-packing chromatic number, χS(G), of G. In this paper, we consider the distance graphs G(ℤ,\2,t\), where t>1 is an odd integer, which has ℤ as its vertex set, and i,j∈ℤ are adjacent if |i-j|∈\2,t\. We determine the S-packing chromatic numbers of the graphs G(ℤ,\2,t\), where S is any sequence with ai∈\1,2\ for all i. In addition, we give lower and upper bounds for the d-distance chromatic numbers of the distance graphs G(ℤ,\2,t\), which in the cases d≥ t-3 give the exact values. Implications for the corresponding S-packing chromatic numbers of the circulant graphs are also discussed.