-packing colorings of cubic graphs

详细信息    查看全文

• 作者：Nicolas Gastineau ^{ngastineau87@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Olivier Togni
• 关键词：Graph ; Coloring ; Packing chromatic number ; Cubic graph
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 October 2016
• 年：2016
• 卷：339
• 期：10
• 页码：2461-2470
• 全文大小：456 K

文摘

Given a non-decreasing sequence S=(s₁,s₂,…,s_k)$S=(s_1,s_2,\dots ,s_k)$ of positive integers, an e838de18456b4d7d27ae7da4d60a973" title="Click to view the MathML source">S$S$-packing coloring   of a graph G$G$ is a mapping c$c$ from V(G)$V\left(G\right)$ to {s₁,s₂,…,s_k}$\{s_1,s_2,\dots ,s_k\}$ such that any two vertices with the i$i$th color are at mutual distance greater than s_i$s_i$, 1≤i≤k$1\le i\le k$. This paper studies e838de18456b4d7d27ae7da4d60a973" title="Click to view the MathML source">S$S$-packing colorings of (sub)cubic graphs. We prove that subcubic graphs are (1,2,2,2,2,2,2)$(1,2,2,2,2,2,2)$-packing colorable and (1,1,2,2,2)$(1,1,2,2,2)$-packing colorable. For subdivisions of subcubic graphs we derive sharper bounds, and we provide an example of a cubic graph of order 38 which is not (1,2,…,12)$(1,2,\dots ,12)$-packing colorable.