TY - JOUR
T1 - Packing Chromatic Number of Subdivisions of Cubic Graphs
AU - Balogh, József
AU - Kostochka, Alexandr
AU - Liu, Xujun
N1 - Research of József Balogh is partially supported by NSF Grant DMS-1500121 and by the Langan Scholar Fund (UIUC). Research of Alexandr Kostochka is supported in part by NSF Grant DMS-1600592 and Grants 18-01-00353A and 16-01-00499 of the Russian Foundation for Basic Research.
PY - 2019/3/15
Y1 - 2019/3/15
N2 - A packing k-coloring of a graph G is a partition of V(G) into sets V 1 , … , V k such that for each 1 ≤ i≤ k the distance between any two distinct x, y∈ V i is at least i+ 1. The packing chromatic number, χ p (G) , of a graph G is the minimum k such that G has a packing k-coloring. For a graph G, let D(G) denote the graph obtained from G by subdividing every edge. The questions on the value of the maximum of χ p (G) and of χ p (D(G)) over the class of subcubic graphs G appear in several papers. Gastineau and Togni asked whether χ p (D(G)) ≤ 5 for any subcubic G, and later Brešar, Klavžar, Rall and Wash conjectured this, but no upper bound was proved. Recently the authors proved that χ p (G) is not bounded in the class of subcubic graphs G. In contrast, in this paper we show that χ p (D(G)) is bounded in this class, and does not exceed 8.
AB - A packing k-coloring of a graph G is a partition of V(G) into sets V 1 , … , V k such that for each 1 ≤ i≤ k the distance between any two distinct x, y∈ V i is at least i+ 1. The packing chromatic number, χ p (G) , of a graph G is the minimum k such that G has a packing k-coloring. For a graph G, let D(G) denote the graph obtained from G by subdividing every edge. The questions on the value of the maximum of χ p (G) and of χ p (D(G)) over the class of subcubic graphs G appear in several papers. Gastineau and Togni asked whether χ p (D(G)) ≤ 5 for any subcubic G, and later Brešar, Klavžar, Rall and Wash conjectured this, but no upper bound was proved. Recently the authors proved that χ p (G) is not bounded in the class of subcubic graphs G. In contrast, in this paper we show that χ p (D(G)) is bounded in this class, and does not exceed 8.
KW - Cubic graphs
KW - Independent sets
KW - Packing coloring
UR - http://www.scopus.com/inward/record.url?scp=85061029347&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85061029347&partnerID=8YFLogxK
U2 - 10.1007/s00373-019-02016-3
DO - 10.1007/s00373-019-02016-3
M3 - Article
AN - SCOPUS:85061029347
SN - 0911-0119
VL - 35
SP - 513
EP - 537
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 2
ER -