Packing chromatic number of distance graphs

Result code in 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>
Alternative codes found
RIV/49777513:23520/12:43897185
Result on the web
<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>

Result language
angličtina
Original language name
Packing chromatic number of distance graphs
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach

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

Similar results(10)