Přejít k obsahu

The packing chromatic number of distance graphs

HOLUB, P. The packing chromatic number of distance graphs. Nový Smokovec, 2011.
Jazyk publikace: eng
Anglický název: The packing chromatic number of distance graphs
Rok vydání: 2011
Autoři: RNDr. Přemysl Holub Ph.D.
Abstrakt CZ: V této práci uvádíme odhady na pakovací chromatické číslo distančních grafů s distanční množinou D{s,t}.
Abstrakt EN: The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that vertices of $G$ can be partitioned into disjoint classes $X_{1}, ..., X_{k}$ where vertices in $X_{i}$ have pairwise distance greater than $i$. We study the packing chromatic number of infinite distance graphs $G(\Z, D)$, 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 D$. In this paper we focus on distance graphs with $D = \{s, t\}$. We improve some results of Togni who initiated the study. For sufficiently large t we show that $\chi_{\rho}(G(\Z, D)) \leq 35$ when $s,t$ are both odd and $\chi_{\rho}(G(\Z, D)) \leq 56$ otherwise. We also give a lower bound 12 for arbitrary s and arbitrary $t \geq 9$ and tighten several gaps for $\chi_{\rho}(G(\Z, D))$ with small $s,t$.
Klíčová slova