Abstract
For 1≤s1≤s2≤…≤sk and a graph G, a packing (s1,s2,…,sk)-coloring of G is a partition of V(G) into sets V1,V2,…,Vk such that, for each 1≤i≤k the distance between any two distinct x,y∈Vi is at least si+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 (s1,s2,…,sk)-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 |
|---|---|
| Pages (from-to) | 8-15 |
| Number of pages | 8 |
| Journal | Discrete Applied Mathematics |
| Volume | 302 |
| DOIs | |
| Publication status | Published - 30 Oct 2021 |
| Externally published | Yes |
Keywords
- Cubic graphs
- Independent sets
- Packing coloring
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver