摘要:
设
\begin{document}$f:V(G) \cup E(G) \to \{ 1, 2,\cdots , k\}$\end{document}是图G的一个正常k−全染色,令权重
$\phi (x) = f(x) + \mathop \Sigma \limits_{e \mathrel\backepsilon x} f(e) + \mathop \Sigma \limits_{y \in N(x)} f(y)$
,其中
$ N(x) = \{ y \in V(G)|xy \in E(G)\} $
. 对任意的边
$ uv \in E(G) $
,如果有
$\phi (u) \ne \phi (v)$
成立,则称
$ f $
为图
$ G $
的一个邻点全和可别正常k正常k−全染色. 图G的邻点全和可区别全色数是指对图
$ G $
进行邻点全和可区别k−全染色所需要的最小色数k,记为
${\rm{ftnd}}{{\rm{i}}_\Sigma }(G)$
. 本研究猜想:对于最大度为
$ \Delta $
的图
$ G $
(
$ {K_2} $
除外),
${\rm{ftnd}}{{\rm{i}}_\Sigma }(G) \leqslant \Delta + 2$
. 研究得到路与路的笛卡尔乘积图和路与圈的笛卡尔乘积图的邻点全和可区别全色数均为
$ \Delta + 1 $
,证实了上述猜想.