Packing chromatic number of distance graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125722" target="_blank" >RIV/00216208:11320/12:10125722 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/49777513:23520/12:43897185

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.dam.2011.11.022" target="_blank" >http://dx.doi.org/10.1016/j.dam.2011.11.022</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2011.11.022" target="_blank" >10.1016/j.dam.2011.11.022</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Packing chromatic number of distance graphs

Popis výsledku v původním jazyce

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 epsilon Z are adjacent if and only if vertical bar i - j vertical bar epsilon 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(Z, D)) {= 35 for sufficiently large odd t and chi(rho)(G(Z, D)) {= 56 for sufficiently large even t. We also give a lower bound 12 for t }= 9 and tighten several gaps for chi(rho)(G(Z. D)) with small t.

Název v anglickém jazyce

Packing chromatic number of distance graphs

Popis výsledku anglicky

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 epsilon Z are adjacent if and only if vertical bar i - j vertical bar epsilon 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(Z, D)) {= 35 for sufficiently large odd t and chi(rho)(G(Z, D)) {= 56 for sufficiently large even t. We also give a lower bound 12 for t }= 9 and tighten several gaps for chi(rho)(G(Z. D)) with small t.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

160

Číslo periodika v rámci svazku

4-5

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

7

Strana od-do

518-524

Kód UT WoS článku

000301211100017

EID výsledku v databázi Scopus

—