





















The Sierpiński product $G \otimes _f H$ of graphs $G$ and $H$ with respect to a function $f \colon V(G)\rightarrow V(H)$ has the vertex set $V(G)\times V(H)$. For every $g\in V(G)$ it contains a disjoint copy $gH$ of $H$, and for every edge $gg'$ of $G$ there is the edge $(g,f(g'))(g',f(g))$ between $gH$ and $g'H$. In this paper, the Sierpiński packing chromatic number is defined as the minimum of $χ_ρ(G\otimes _f H)$ over all functions $f$, where $χ_ρ(X)$ is the packing chromatic number of $X$. The upper Sierpiński packing chromatic number is analogously defined as the maximum corresponding value. The (upper) Sierpiński packing chromatic number is determined for all Sierpiński product graphs whose both factors are complete. Sierpiński product graphs whose factors are paths or stars are also studied. Their Sierpiński packing chromatic number is always $3$, while their upper Sierpiński packing chromatic number is bounded from below and above. It is also proved that for a given graph $G$, it can be checked in polynomial time whether $G$ has a representation as a Sierpiński product graphs both factors of which being trees.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。