Packing chromatic number versus chromatic and clique number

被引：11

作者：

Bresar, Bostjan ^{[1
,2
]}

Klavzar, Sandi ^{[1
,2
,3
]}

Rall, Douglas F. ^{[4
]}

Wash, Kirsti ^{[5
]}

机构：

[1] Univ Maribor, Fac Nat Sci & Math, Maribor, Slovenia

[2] Inst Math Phys & Mech, Ljubljana, Slovenia

[3] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia

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

[5] Western New England Univ, Dept Math, Springfield, MA USA

来源：

AEQUATIONES MATHEMATICAE | 2018年 / 92卷 / 03期

关键词：

Packing chromatic number; Chromatic number; Clique number; Independence number; Mycielskian; HEXAGONAL LATTICE; DISTANCE GRAPHS; COLORINGS; PRODUCT;

D O I：

10.1007/s00010-017-0520-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The packing chromatic number of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets , , where each is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that , , and . If so, we say that (a, b, c) is realizable. It is proved that implies , and that triples and are not realizable as soon as . Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound chi(rho)(G) on in terms of Delta(G) and alpha(G) is also proved.

引用

页码：497 / 513

页数：17

共 31 条

[1] The packing coloring problem for lobsters and partner limited graphs [J].

Argiroffo, G. ;

Nasini, G. ;

Torres, P. .

DISCRETE APPLIED MATHEMATICS, 2014, 164 :373-382

[2] Connectivity of the Mycielskian of a graph [J].

Balakrishnan, R. ;

Raj, S. Francis .

DISCRETE MATHEMATICS, 2008, 308 (12) :2607-2610

[3]

Balogh J., 2017, ARXIV170309873

[4] On the packing chromatic number of Cartesian products, hexagonal lattice, and trees [J].

Bresar, Bostjan ;

Klavzar, Sandi ;

Rall, Douglas F. .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (17) :2303-2311

[5] Packing chromatic number under local changes in a graph [J].

Bresar, Bostjan ;

Klavzar, Sandi ;

Rall, Douglas F. ;

Washe, Kirsti .

DISCRETE MATHEMATICS, 2017, 340 (05) :1110-1115

[6]

Bresar B, 2017, AEQUATIONES MATH, V91, P169, DOI 10.1007/s00010-016-0461-8

[7] Packing Chromatic Number of Base-3 SierpiA"ski Graphs [J].

Bresar, Bostjan ;

Klavzar, Sandi ;

Rall, Douglas F. .

GRAPHS AND COMBINATORICS, 2016, 32 (04) :1313-1327

[8]

Doslic T., 2005, Discussiones Mathematicae Graph Theory, V25, P261, DOI 10.7151/dmgt.1279

[9] The packing coloring of distance graphs D(k, t) [J].

Ekstein, Jan ;

Holub, Premysl ;

Togni, Olivier .

DISCRETE APPLIED MATHEMATICS, 2014, 167 :100-106

[10] Complexity of the packing coloring problem for trees [J].

Fiala, Jiri ;

Golovach, Petr A. .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (07) :771-778

← 1 2 3 4 →