| Title: | $S$-packing colorings of distance graphs with distance sets of cardinality $2$ |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Ferme, Jasmina (Author)
ID Holub, Přemysl (Author)
ID Jakovac, Marko (Author)
ID Melicharová, Petra (Author) |
|---|
| Files: |  PDF - Presentation file, download (771,39 KB)
MD5: 4C734DCFA049C99F55035E4590242882
 URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0096300324006611
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | For a non-decreasing sequence $S=(s_1,s_2,\ldots)$ of positive integers, a partition of the vertex set of a graph $G$ into subsets $X_1,\ldots, X_\ell$, such that vertices in $X_i$ are pairwise at distance greater than $s_i$ for every $i\in\{1,\ldots,\ell\}$, is called an $S$-packing $\ell$-coloring of $G$. The minimum $\ell$ for which $G$ admits an $S$-packing $\ell$-coloring is called the $S$-packing chromatic number of $G$. In this paper, we consider $S$-packing colorings of the integer distance graphs with respect two positive integers $k$ and $t$, which are the graphs whose vertex set is $\mathbb{Z}$, and two vertices $x,y\in \mathbb{Z}$ are adjacent whenever $|x-y|\in\{k,t\}$. We complement partial results from two earlier papers, thus determining all values of the $S$-packing chromatic numbers of these distance graphs for all sequence $S$ such that $s_i\le 2$ for all $i$. In particular, if $S=(1,1,2,2,\ldots)$, then the $S$-packing chromatic number is $2$ if $k+t$ is even, and $4$ otherwise, while if $S=(1,2,2,\ldots)$, then the $S$-packing chromatic number is $5$, unless $\{k,t\}=\{2,3\}$ when it is $6$; when $S=(2,2,2,\ldots)$, the corresponding formula is more complex. |
|---|
| Keywords: | S-packing coloring, S-packing chromatic number, distance graph, distance coloring |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.04.2025 |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | 13 str. |
|---|
| Numbering: | Vol. 490, article no. 129200 |
|---|
| PID: | 20.500.12556/DiRROS-20865  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0096-3003 |
|---|
| DOI: | 10.1016/j.amc.2024.129200 |
|---|
| COBISS.SI-ID: | 216160771 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 22.11.2024 |
|---|
| Views: | 37 |
|---|
| Downloads: | 14 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
