| Naslov: | $S$-packing colorings of distance graphs with distance sets of cardinality $2$ |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Ferme, Jasmina (Avtor)
ID Holub, Přemysl (Avtor)
ID Jakovac, Marko (Avtor)
ID Melicharová, Petra (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (771,39 KB)
MD5: 4C734DCFA049C99F55035E4590242882
 URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0096300324006611
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | S-packing coloring, S-packing chromatic number, distance graph, distance coloring |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.04.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 13 str. |
|---|
| Številčenje: | Vol. 490, article no. 129200 |
|---|
| PID: | 20.500.12556/DiRROS-20865  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0096-3003 |
|---|
| DOI: | 10.1016/j.amc.2024.129200 |
|---|
| COBISS.SI-ID: | 216160771 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 22.11.2024 |
|---|
| Število ogledov: | 38 |
|---|
| Število prenosov: | 15 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
