S-Packing Colorings of Cubic Graphs

Nicolas Gastineau (1) , Olivier Togni (2, 3)

1 GrAMA - Graphes, Algorithmes et Multi-Agents
2 Le2i - Laboratoire Electronique, Informatique et Image [UMR6306]
3 LIB - Laboratoire d'Informatique de Bourgogne [Dijon]

Given a non-decreasing sequence $S=(s_1,s_2, \ldots, s_k)$ of positive integers, an {\em $S$-packing coloring} of a graph $G$ is a mapping $c$ from $V(G)$ to $\{s_1,s_2, \ldots, s_k\}$ such that any two vertices with color $s_i$ are at mutual distance greater than $s_i$, $1\le i\le k$. This paper studies $S$-packing colorings of (sub)cubic graphs. We prove that subcubic graphs are $(1,2,2,2,2,2,2)$-packing colorable and $(1,1,2,2,3)$-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,\ldots,12)$-packing colorable.

Mots clés: cubic graph; packing chromatic number; coloring

Domaines: Mathématique discrète [cs.DM]

Nicolas Gastineau, Olivier Togni. S-Packing Colorings of Cubic Graphs. Discrete Mathematics, 2016, 339 (10), pp.2461-2470. ⟨10.1016/j.disc.2016.04.017⟩. ⟨hal-00967446v2⟩