论文标题
包装$（1,1,2,4）$ - 亚立管外平面图的着色
Packing $(1,1,2,4)$-coloring of subcubic outerplanar graphs
论文作者
论文摘要
以$ 1 \ leq s_1 \ le s_2 \ le \ ldots \ le \ le s_k $和图$ g $，包装$（s_1，s_1，s_2，\ ldots，s_k）$ - 颜色$ g $是$ v（g）$ v（g）$ v_1 $ v_1 $ v_1，v_2 $ v_ $ v_ for eq for ldots ldots，ve_的分区， k $，任何两个不同的$ x，y \ in v_i $之间的距离至少为$ s_i + 1 $。图形$ g $的包装色号，$χ_p（g）$是最小的$ k $，因此$ g $具有包装$（1,2，\ ldots，k）$ - 颜色。众所周知，有最高学位的树木和亚立管图$ g $，带有任意大$χ_p（g）$的树。最近，有一系列有关包装$（s_1，s_2，\ ldots，s_k）$的论文 - 在各个类中的亚地图的颜色。我们表明，每2美元连接的亚立方体外平面图都有一个包装$（1,1,2）$ - 着色，并且每个亚立方体外平面图都包装$（1,1,2,4）$ - 可颜色。从某种意义上说，我们的结果很清晰，因为有$ 2 $连接的亚立方体外平面图没有包装$（1,1,3）$ - 可着色，并且有未包装$（1,1,1,2,5）$的次立皮外平面图。我们还显示了没有包装$（1,2,2,4）$的$（1,2,2,4）$的亚基外平面图 - 可着色且不包装$（1,1,3,4）$ - 可着色。
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, $χ_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 $χ_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. We also show subcubic outerplanar graphs that are not packing $(1,2,2,4)$-colorable and not packing $(1,1,3,4)$-colorable.
