Přejít k obsahu


The packing coloring of distance graphs D(k, t)

Citace: EKSTEIN, J., HOLUB, P., TOGNI, O. The packing coloring of distance graphs D(k, t). Discrete Applied Mathematics, 2014, roč. 167, č. April, s. 100-106. ISSN: 0166-218X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: The packing coloring of distance graphs D(k, t)
Rok vydání: 2014
Autoři: RNDr. Jan Ekstein Ph.D. , RNDr. Přemysl Holub Ph.D. , Olivier Togni Ph.D.
Abstrakt CZ: Pakovací chromatické číslo $\chi_{\rho}(G)$ grafu $G$ je nejmenší celé číslo $p$ takové, že vrcholy grafu $G$ lze rozdělit do disjunktních tříd $X_{1}, ..., X_{p}$, kde vrcholy v $X_{i}$ jsou ve vzdálenosti větší než $i$ v $G$. Pro $k < t$ studujeme pakovací chromatické číslo distančních grafů $D(k, t)$, tj. grafů s množinou vrcholů $\Z$, kde dva vrcholy $i, j \in \Z$ jsou sousední právě tehdy, když |i - j| \in \{k, t\}$. V článku se zobecní výsledky Eksteina a kol. pro grafy $D (1, t)$. Pro dostatečně velké $t$ dokážeme, že $\chi_{\rho}(D(k, t)) \leq 30$ pro obě $k$, $t$ liché a $\chi_{\rho}(D(k, t)) \leq 56$ pro právě jedno z $k$, $t$ liché. Rovněž stanovíme dolní a horní meze na $\chi_{\rho}(D(k, t))$ pro malé hodnoty $k$ a $t$.
Abstrakt EN: The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $p$ such that vertices of $G$ can be partitioned into disjoint classes $X_{1}, ..., X_{p}$ where vertices in $X_{i}$ have pairwise distance greater than $i$. For $k < t$ we study the packing chromatic number of infinite distance graphs $D(k, t)$, i.e. graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in \{k, t\}$. We generalize results by Ekstein et al. for graphs $D (1, t)$. For sufficiently large $t$ we prove that $\chi_{\rho}(D(k, t)) \leq 30$ for both $k$, $t$ odd, and that $\chi_{\rho}(D(k, t)) \leq 56$ for exactly one of $k$, $t$ odd. We also give some upper and lower bounds for $\chi_{\rho}(D(k, t))$ with small $k$ and $t$.
Klíčová slova

Zpět

Patička