On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

被引：63

作者：

Bresar, Bostjan

Klavzar, Sandi

Rall, Douglas F.

机构：

[1] Univ Maribor, FEECS, SLO-2000 Maribor, Slovenia

[2] Univ Maribor, FNM, Dept Math & Comp Sci, SLO-2000 Maribor, Slovenia

[3] Furman Univ, Dept Math, Greenville, SC 29613 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2007年 / 155卷 / 17期

关键词：

packing chromatic number; Cartesian product of graphs; hexagonal lattice; subdivision graph; tree; computational complexity;

D O I：

10.1016/j.dam.2007.06.008

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The packing chromatic number chi(p)(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：2303 / 2311

页数：9

共 15 条

[1]

[Anonymous], PRODUCT GRAPHS STRUC

[2] On the independence graph of a graph [J].

Bresar, B ;

Zmazek, B .

DISCRETE MATHEMATICS, 2003, 272 (2-3) :263-268

[3]

FIALA J, 2007, COMMUNICATION

[4]

FINBOW A, 2007, MANUSCRIPT

[5] Distributive online channel assignment for hexagonal cellular networks with constraints [J].

Fitzpatrick, S ;

Jeannen, J ;

Nowakowski, R .

DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) :84-91

[6]

GODDARD W, IN PRESS ARS COMBIN

[7]

Hagauer J, 1996, ARS COMBINATORIA, V43, P149

[8] Perfect r-domination in the Kronecker product of three cycles [J].

Jha, PK .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-FUNDAMENTAL THEORY AND APPLICATIONS, 2002, 49 (01) :89-92

[9]

Klavzar S, 2005, ARS COMBINATORIA, V74, P173

[10]

Martin SP, 2001, ARS COMBINATORIA, V60, P73

← 1 2 →