Subdivision into i-packings and S-packing chromatic number of some lattices

被引：17

作者：

Gastineau, Nicolas ^{[1
]}

Kheddouci, Hamamache ^{[2
]}

Togni, Olivier ^{[1
]}

机构：

[1] Univ Bourgogne, LE2I, UMR 6306, CNRS, F-21078 Dijon, France

[2] Univ Lyon 1, CNRS, LIRIS, UMR5205, F-69622 Villeurbanne, France

来源：

ARS MATHEMATICA CONTEMPORANEA | 2015年 / 9卷 / 02期

关键词：

Packing chromatic number; i-packing; hexagonal lattice; square lattice; triangular lattice; distance coloring; GRAPHS; COLORINGS;

D O I：

10.26493/1855-3974.436.178

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An i-packing in a graph G is a set of vertices at pairwise distance greater than i. For a nondecreasing sequence of integers S = (s(1), s(2),...), the S-packing chromatic number of a graph G is the least integer k such that there exists a coloring of G into k colors where each set of vertices colored i, i = 1,..., k, is an s(i)-packing. This paper describes various subdivisions of an i-packing into j-packings (j>i) for the hexagonal, square and triangular lattices. These results allow us to bound the S-packing chromatic number for these graphs, with more precise bounds and exact values for sequences S = (s(i), i epsilon N*), s(i) = d+[(i-1)/n].

引用

页码：331 / 354

页数：24