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

DOI10.1016/J.DAM.2021.04.001MaRDI QIDQ2028095zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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)