|
Citation:
|
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
|
|
Type:
|
ČLÁNEK
|
|
Language:
|
eng
|
|
English title:
|
Packing Chromatic Number of Distance Graphs
|
|
Publication year:
|
2012
|
|
Authors:
|
RNDr. Jan Ekstein Ph.D.
,
RNDr. Přemysl Holub Ph.D.
|
|
Abstract 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.
|
|
Abstract 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
|
|
Keywords
|
|