























A packing $k$-coloring of a graph $G$ is a partition of $V(G)$ into sets $V_1,\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 $i+1$. The packing chromatic number, $χ_p(G)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. For a graph $G$, let $D(G)$ denote the graph obtained from $G$ by subdividing every edge. The questions on the value of the maximum of $χ_p(G)$ and of $χ_p(D(G))$ over the class of subcubic graphs $G$ appear in several papers. Gastineau and Togni asked whether $χ_p(D(G))\leq 5$ for any subcubic $G$, and later Bresar, Klavzar, Rall and Wash conjectured this, but no upper bound was proved. Recently the authors proved that $χ_p(G)$ is not bounded in the class of subcubic graphs $G$. In contrast, in this paper we show that $χ_p(D(G))$ is bounded in this class, and does not exceed $8$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。