Přejít k obsahu


Packing Chromatic Number of Distance Graphs

Citace: [] EKSTEIN, J., HOLUB, P., LIDICKÝ, B. Packing Chromatic Number of Distance Graphs. DISCRETE APPLIED MATHEMATICS, 2012, roč. 160, č. 4-5, s. 518-524. ISSN: 0166-218X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Packing Chromatic Number of Distance Graphs
Rok vydání: 2012
Autoři: RNDr. Jan Ekstein Ph.D. , RNDr. Přemysl Holub Ph.D. , RNDr. Bernard Lidický Ph.D.
Abstrakt CZ: Pakovací chromatické číslo ??(G) grafu G je nejmenší celé číslo k takové, že vrcholy G lze rozdělit do navzájem disjunktních množin X1, ..., Xk, kde vrcholy v Xi jsou ve vzdálenosti větší než i v G. Studujeme pakovací chromatické číslo někonečných distančních grafů G(Z, D), tj. grafů s množinou Z celých čísel jako množinou vrcholů, v kterých dva vrcholy i, j ? Z jsou sousední právě tehdy, když |i ? j| ? D. V tomto článku zkoumáme distanční grafy s D = {1, t}. Zlepšíme některé výsledky od Togniho. Je ukázáno, že ??(G(Z, D)) ? 35 pro dostatečně velké liché t a ??(G(Z, D)) ? 56 pro dostatečně velké sudé t. Rovněž uvedeme dolní mez 12 pro t ? 9 a některé dolní a horní meze pro ??(G(Z, D)) pro malé hodnoty t.
Abstrakt EN: The packing chromatic number ??(G) of a graph G is the smallest integer k such that vertices of G can be partitioned into disjoint classes X1, ..., Xk where vertices in Xi 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 ? Z are adjacent if and only if |i ? j| ? 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 ??(G(Z, D)) ? 35 for sufficiently large odd t and ??(G(Z, D)) ? 56 for sufficiently large even t. We also give a lower bound 12 for t ? 9 and tighten several gaps for ??(G(Z, D)) with small t. ? 2011 Elsevier
Klíčová slova

Zpět

Patička