Packing Chromatic Number of Subdivisions of Cubic Graphs

József Balogh, Alexandr Kostochka, Xujun Liu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)513-537
Number of pages25
JournalGraphs and Combinatorics
Issue number2
Publication statusPublished - 15 Mar 2019
Externally publishedYes


  • Cubic graphs
  • Independent sets
  • Packing coloring

Cite this