Packing (1,1,2,4)-coloring of subcubic outerplanar graphs

Alexandr Kostochka, Xujun Liu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)8-15
Number of pages8
JournalDiscrete Applied Mathematics
Volume302
DOIs
Publication statusPublished - 30 Oct 2021
Externally publishedYes

Keywords

  • Cubic graphs
  • Independent sets
  • Packing coloring

Cite this