Packing chromatic number under local changes in a graph

被引：28
作者：
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
相关论文
共 50 条
  • [1] Packing chromatic number, (1,1,2,2)-colorings, and characterizing the Petersen graph
    Bresar, Bostjan
    Klavzar, Sandi
    Rall, Douglas F.
    Wash, Kirsti
    AEQUATIONES MATHEMATICAE, 2017, 91 (01) : 169 - 184
  • [2] Packing chromatic number versus chromatic and clique number
    Bresar, Bostjan
    Klavzar, Sandi
    Rall, Douglas F.
    Wash, Kirsti
    AEQUATIONES MATHEMATICAE, 2018, 92 (03) : 497 - 513
  • [3] The packing chromatic number of hypercubes
    Torres, Pablo
    Valencia-Pabon, Mario
    DISCRETE APPLIED MATHEMATICS, 2015, 190 : 127 - 140
  • [4] On the packing chromatic number of subcubic outerplanar graphs
    Gastineau, Nicolas
    Holub, Premysl
    Togni, Olivier
    DISCRETE APPLIED MATHEMATICS, 2019, 255 : 209 - 221
  • [5] Packing chromatic number versus chromatic and clique number
    Boštjan Brešar
    Sandi Klavžar
    Douglas F. Rall
    Kirsti Wash
    Aequationes mathematicae, 2018, 92 : 497 - 513
  • [6] On the packing chromatic number of square and hexagonal lattice
    Korze, Danilo
    Vesel, Aleksander
    ARS MATHEMATICA CONTEMPORANEA, 2014, 7 (01) : 13 - 22
  • [7] Graphs that are Critical for the Packing Chromatic Number
    Bresar, Bostjan
    Ferme, Jasmina
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (02) : 569 - 589
  • [8] On the packing chromatic number of Moore graphs
    Fresan-Figueroa, J.
    Gonzalez-Moreno, D.
    Olsen, M.
    DISCRETE APPLIED MATHEMATICS, 2021, 289 (289) : 185 - 193
  • [9] Packing chromatic number of distance graphs
    Ekstein, Jan
    Holub, Premysl
    Lidicky, Bernard
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (4-5) : 518 - 524
  • [10] PACKING CHROMATIC NUMBER OF TRANSFORMATION GRAPHS
    Durgun, Derya D.
    Ozen Dortok, H. Busra
    THERMAL SCIENCE, 2019, 23 : S1991 - S1995
12345