pith. sign in

arxiv: 1608.05573 · v1 · pith:Q67OAIFFnew · submitted 2016-08-19 · 🧮 math.CO

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

classification 🧮 math.CO
keywords generalizedgraphnumberpackingchromaticconjecturecyclesproved
0
0 comments X
read the original 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,\ldots,\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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.