## 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 language | English (US) |
---|---|

Pages (from-to) | 513-537 |

Number of pages | 25 |

Journal | Graphs and Combinatorics |

Volume | 35 |

Issue number | 2 |

DOIs | |

State | Published - Mar 15 2019 |

## Keywords

- Cubic graphs
- Independent sets
- Packing coloring

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics