论文标题
$ s $ - 包装色顶点临界图
$S$-packing chromatic vertex-critical graphs
论文作者
论文摘要
对于非降低积极整数的顺序，$ s =（s_1，s_2，\ ldots）$，{\ em $ s $ - 包装彩色数字} $χ_s（g）$ g $的$ g $是最小的integer $ k $ $ k $的最小$ k $ $ g $的$ g $可以分配给$ $ $ x_i $ x_i in [$ x_i in] $ x_i $在距离大于$ s_i $的距离上是成对的。在本文中，我们介绍了$ s $ - 包装色顶点临界图，$χ_{s} $ - 对于简短而言至关重要，如$χ_{s}（g-u）<χ_{s}（s}（s}（g）$，v（g）$ in v（g）$的图形。这扩展了填料彩色顶点临界图的早期概念。我们表明，如果$ g $是$χ_{s} $ - critical，则设置$ \ {χ_{s}（g） - χ_{s}（g-u）; \，u \ in V（g）\} $几乎可以是任意的。如果$ g $是$χ_{s} $ - critical和$χ_{s}（g）= k $（$ k \ in \ mathbb {n} $），则$ g $称为$ k $ - $ c $ - $χ_{s} $ - crialital- critical。我们表征$ 3 $ - $χ_{s} $ - 关键图形，部分表征$ 4 $ - $χ_{s} $ - $ S_1> 1 $时的关键图。我们还处理$ k $ - $χ_{s} $ - 树木和毛毛虫的关键性。
For a non-decreasing sequence of positive integers $S = (s_1,s_2,\ldots)$, the {\em $S$-packing chromatic number} $χ_S(G)$ of $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $X_i$, $i \in [k]$, where vertices in $X_i$ are pairwise at distance greater than $s_i$. In this paper we introduce $S$-packing chromatic vertex-critical graphs, $χ_{S}$-critical for short, as the graphs in which $χ_{S}(G-u)<χ_{S}(G)$ for every $u\in V(G)$. This extends the earlier concept of the packing chromatic vertex-critical graphs. We show that if $G$ is $χ_{S}$-critical, then the set $\{ χ_{S}(G)-χ_{S}(G-u); \, u\in V(G) \}$ can be almost arbitrary. If $G$ is $χ_{S}$-critical and $χ_{S}(G)=k$ ($k\in \mathbb{N}$), then $G$ is called $k$-$χ_{S}$-critical. We characterize $3$-$χ_{S}$-critical graphs and partially characterize $4$-$χ_{S}$-critical graphs when $s_1>1$. We also deal with $k$-$χ_{S}$-criticality of trees and caterpillars.
