Department of

May 2020 June 2020July 2020Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa SuMoTu We Th Fr Sa 1 2 1 2 3 4 5 6 1 2 3 4 3 4 5 6 7 8 9 7 8 9 10 11 12 13 567 8 9 10 11 10 11 12 13 14 15 16 14 15 16 17 18 19 20 12 13 14 15 16 17 18 17 18 19 20 21 22 23 21 22 23 24 25 26 27 19 20 21 22 23 24 25 24 25 26 27 28 29 30 28 29 30 26 27 28 29 30 31 31

Tuesday, June 9, 2020

**Abstract:** For $1\leq s_1 \le s_2 \le \ldots \le s_k$ and a graph $G$, a packing $(s_1, s_2, \ldots, s_k)$-coloring of $G$, is a partition of $V(G)$ into sets $V_1, V_2, \ldots, V_k$ such that for each $1\leq i \leq k$ the distance between any two distinct $x,y\in V_i$ is at least $s_i + 1$. The packing chromatic number, $\chi_p(G)$, of a graph $G$ is the smallest $k$ such that $G$ has a packing $(1,2, \ldots, k)$-coloring. It is known that there are trees of maximum degree 4 and subcubic graphs $G$ with arbitrarily large $\chi_p(G)$. Recently, there was a series of papers on packing $(s_1, s_2, \ldots, 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. This is joint work with Alexandr Kostochka.

Please contact Sean English at SEnglish@illinois.edu for the Zoom information.