Packing Chromatic Number of Subdivisions of Cubic Graphs

Research output: Contribution to journalArticle

Abstract

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 (US)
Pages (from-to)513-537
Number of pages25
JournalGraphs and Combinatorics
Volume35
Issue number2
DOIs
StatePublished - Mar 15 2019

Keywords

  • Cubic graphs
  • Independent sets
  • Packing coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Packing Chromatic Number of Subdivisions of Cubic Graphs'. Together they form a unique fingerprint.

  • Cite this