## Abstract

For 1≤s_{1}≤s_{2}≤…≤s_{k} and a graph G, a packing (s_{1},s_{2},…,s_{k})-coloring of G is a partition of V(G) into sets V_{1},V_{2},…,V_{k} such that, for each 1≤i≤k the distance between any two distinct x,y∈V_{i} is at least s_{i}+1. The packing chromatic number, χ_{p}(G), of a graph G is the smallest k such that G has a packing (1,2,…,k)-coloring. It is known that there are trees of maximum degree 4 and subcubic graphs G with arbitrarily large χ_{p}(G). Recently, there was a series of papers on packing (s_{1},s_{2},…,s_{k})-colorings of subcubic graphs in various classes. We show that every 2-connected subcubic outerplanar graph has a packing (1,1,2)-coloring and every subcubic outerplanar graph is packing (1,1,2,4)-colorable. Our results are sharp in the sense that there are 2-connected subcubic outerplanar graphs that are not packing (1,1,3)-colorable and there are subcubic outerplanar graphs that are not packing (1,1,2,5)-colorable. We also show subcubic outerplanar graphs that are not packing (1,2,2,4)-colorable and not packing (1,1,3,4)-colorable.

Original language | English (US) |
---|---|

Pages (from-to) | 8-15 |

Number of pages | 8 |

Journal | Discrete Applied Mathematics |

Volume | 302 |

DOIs | |

State | Published - Oct 30 2021 |

## Keywords

- Cubic graphs
- Independent sets
- Packing coloring

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics