Přejít k obsahu
﻿

### Packing Chromatic Number of Distance Graphs

 Citace: [] EKSTEIN, J. Packing Chromatic Number of Distance Graphs. 2011. PŘEDNÁŠKA, POSTER eng Packing Chromatic Number of Distance Graphs 2011 RNDr. Jan Ekstein Pakovací chromatické číslo $\chi_{\rho}(G)$ grafu $G$ je nejmenší přirozené číslo $k$ takové, že vrcholy $G$ lze rozdělit do disjunktních množin $X_{1}, ..., X_{k}$, kde vrcholy v $X_{i}$ mají po dvou vzdálenost větší než $i$. Zabýváme se pakovacím chormatickým číslem nekonečných distančních grafů $G(\mathbb{Z}, D)$, tj. grafů s množinou $\mathbb{Z}$ celých čísel jako množinou vrcholů a dva různé vrcholy jsou sousední v $G(\mathbb{Z}, D)$ právě tehdy, když $|i - j| \in D$. Konkrétně uvažujeme distanční grafy s množinou $D = \{1, t\}$. Zlepšíme některé výsledky Togniho, který začal se studiem pakovacího barvení těchto grafů. Ukážeme, že $\chi_{\rho}(G(\mathbb{Z}, D)) \leq 35$ pro dostatečně velké liché $t$ a $\chi_{\rho}(G(\mathbb{Z}, D)) \leq 56$ pro dostatečně velké sudé $t$. Rovněž uvedeme dolní mez 12 pro $t \geq 9$ a stanovíme některé nové dolní a horní meze pro $\chi_{\rho}(G(\mathbb{Z}, D))$ pro malé hodnoty $t$. 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(\mathbb{Z}, D)$, i.e. graphs with the set $\mathbb{Z}$ of integers as vertex set and in which two distinct vertices $i, j \in \mathbb{Z}$ are adjacent if and only if $|i - j| \in D$. In this paper we focus on distance graphs with $D = \{1, t\}$. We improve some results of Togni who initiated the study. It is shown that $\chi_{\rho}(G(\mathbb{Z}, D)) \leq 35$ for sufficiently large odd $t$ and $\chi_{\rho}(G(\mathbb{Z}, D)) \leq 56$ for sufficiently large even $t$. We also give a lower bound 12 for $t \geq 9$ and tighten several gaps for $\chi_{\rho}(G(\mathbb{Z}, D))$ with small $t$.

Zpět