Packing chromatic number, $(1,1,2,2)$-colorings, and characterizing the Petersen graph

Abstract

The packing chromatic number ${\chi }_{\rho }(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets ${\Pi }_1,\dots ,{\Pi }_k$, where ${\Pi }_i$, $i\in [k]$, is an $i$-packing. The following conjecture is posed and studied: if $G$ is a subcubic graph, then ${\chi }_{\rho }(S(G))\le 5$, where $S(G)$ is the subdivision of $G$. The conjecture is proved for all generalized prisms of cycles. To get this result it is proved that if $G$ is a generalized prism of a cycle, then $G$ is $(1,1,2,2)$-colorable if and only if $G$ is not the Petersen graph. The validity of the conjecture is further proved for graphs that can be obtained from generalized prisms in such a way that one of the two $n$-cycles in the edge set of a generalized prism is replaced by a union of cycles among which at most one is a 5-cycle. The packing chromatic number of graphs obtained by subdividing each of its edges a fixed number of times is also considered.

16 pages, 4 figures

References in corpus (1)

• Packing chromatic number under local changes in a graph

Cited by in corpus (1)

• Packing $(1,1,2,2)$-coloring of some subcubic graphs