Packing chromatic number under local changes in a graph

被引：30

作者：

Bresar, Bostjan ^{[1
,2
]}

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

Rall, Douglas F. ^{[4
]}

Washe, 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] Trinity Coll, Dept Math, Hartford, CT 06106 USA

来源：

DISCRETE MATHEMATICS | 2017年 / 340卷 / 05期

关键词：

Packing chromatic number; Cubic graph; Subdivision; Contraction; HEXAGONAL LATTICE; DISTANCE GRAPHS; COLORINGS; PRODUCT;

D O I：

10.1016/j.disc.2016.09.030

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The packing chromatic number chi(rho)(G) of a graph G is the smallest integer k such that there exists.a k-vertex coloring of G in which any two vertices receiving color i are at distance at least i + 1. It is proved that in the class of subcubic graphs the packing chromatic number is bigger than 13, thus answering an open problem from Gastineau and Togni (2016). In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if S-e(G) is the graph obtained from a graph G by subdividing its edge e, then [chi(rho)(G)/2] + 1 <= chi(rho)(S-e(G)) <= chi(rho)(G) + 1. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：1110 / 1115

页数：6

共 16 条

[1] SOME LARGE GRAPHS WITH GIVEN DEGREE AND DIAMETER [J].

ALEGRE, I ;

FIOL, MA ;

YEBRA, JLA .

JOURNAL OF GRAPH THEORY, 1986, 10 (02) :219-224

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

Argiroffo, G. ;

Nasini, G. ;

Torres, P. .

DISCRETE APPLIED MATHEMATICS, 2014, 164 :373-382

[3] 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

[4] 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

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

Ekstein, Jan ;

Holub, Premysl ;

Togni, Olivier .

DISCRETE APPLIED MATHEMATICS, 2014, 167 :100-106

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

Fiala, Jiri ;

Golovach, Petr A. .

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

[7] The packing chromatic number of infinite product graphs [J].

Fiala, Jiri ;

Klavzar, Sandi ;

Lidicky, Bernard .

EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) :1101-1113

[8] S-packing colorings of cubic graphs [J].

Gastineau, Nicolas ;

Togni, Olivier .

DISCRETE MATHEMATICS, 2016, 339 (10) :2461-2470

[9]

Goddard W, 2008, ARS COMBINATORIA, V86, P33

[10] A lower bound for the packing chromatic number of the Cartesian product of cycles [J].

Jacobs, Yoland ;

Jonck, Elizabeth ;

Joubert, Ernst J. .

CENTRAL EUROPEAN JOURNAL OF MATHEMATICS, 2013, 11 (07) :1344-1357

← 1 2 →