S-packing colorings of distance graphs G ( Z , \ 2 , t \ )

DOI10.1016/J.DAM.2021.04.001zbMATH Open1465.05061arXiv2005.10491OpenAlexW3155130972MaRDI QIDQ2028095FDOQ2028095

Authors: Boštjan Brešar, Jasmina Ferme, Karolína Kamenická 

Publication date: 31 May 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Given a graph $G$ and a non-decreasing sequence $S=(a_1,a_2,ldots)$ of positive integers, the mapping $f:V(G)ightarrow1,ldots,k$ is an $S$-packing $k$-coloring of $G$ if for any distinct vertices $u,vinV(G)$ with $f(u)=f(v)=i$ the distance between $u$ and $v$ in $G$ is greater than $a_i$. The smallest $k$ such that $G$ has an $S$-packing $k$-coloring is the $S$-packing chromatic number, $ch{i}_S(G)$, of $G$. In this paper, we consider the distance graphs $G(mathbbZ,2,t)$, where $t>1$ is an odd integer, which has $mathbbZ$ as its vertex set, and $i,jinmathbbZ$ are adjacent if $|i-j|in2,t$. We determine the $S$-packing chromatic numbers of the graphs $G(mathbbZ,2,t)$, where $S$ is any sequence with $a_{i}in1,2$ for all $i$. In addition, we give lower and upper bounds for the $d$-distance chromatic numbers of the distance graphs $G(mathbbZ,2,t)$, which in the cases $dget-3$ give the exact values. Implications for the corresponding $S$-packing chromatic numbers of the circulant graphs are also discussed.

Full work available at URL: https://arxiv.org/abs/2005.10491

Recommendations

• On \(S\)-packing colourings of distance graphs \(D (1, t)\) and \(D (1, 2, t)\)
• On packing colorings of distance graphs
• Packing chromatic number of distance graphs
• The packing coloring of distance graphs \(D(k,t)\)
• A survey on packing colorings

zbMATH Keywords

distance graphdistance coloring\(S\)-packing chromatic number\(S\)-packing coloring

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Isomorphism of circulant graphs and digraphs
• The packing chromatic number of infinite product graphs
• Packing chromatic number of subdivisions of cubic graphs
• Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs
• A note on packing chromatic number of the square lattice
• Dichotomies properties on computational complexity of \(S\)-packing coloring problems
• A survey on the distance-colouring of graphs
• A note on \(S\)-packing colorings of lattices
• The \(S\)-packing chromatic number of a graph
• \(S\)-packing colorings of cubic graphs
• Broadcast chromatic numbers of graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• On the packing chromatic number of some lattices
• The packing coloring of distance graphs \(D(k,t)\)
• On the packing chromatic number of square and hexagonal lattice
• Packing chromatic number of distance graphs
• On packing colorings of distance graphs
• Modeling the packing coloring problem of graphs
• Subdivision into \(i\)-packings and \(S\)-packing chromatic number of some lattices
• Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph
• The packing chromatic number of the infinite square lattice is between 13 and 15
• On the packing chromatic number of subcubic outerplanar graphs
• 2-distance colorings of integer distance graphs
• Perfect colorings of the infinite circulant graph with distances 1 and 2

Cited In (7)

• A survey on packing colorings
• On packing colorings of distance graphs
• A characterization of 4-\(\chi_S\)-vertex-critical graphs for packing sequences with \(s_1 = 1\) and \(s_2 \geq 3\)
• Gröbner bases techniques for an \(S\)-packing \(k\)-coloring of a graph
• On \(S\)-packing colourings of distance graphs \(D (1, t)\) and \(D (1, 2, t)\)
• The \(S\)-packing chromatic number of a graph
• The packing coloring of distance graphs \(D(k,t)\)

This page was built for publication: \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028095)