几类笛卡尔乘积图的邻点全和可区别全染色

摘要

设f:V（G）∪E（G）→[k]是图G的一个非正常的k-全染色，令权重■，其中，N（x）={y∈V（G）|xy∈E（G）}对任意的边uv∈E（G），如果有φ（u）≠φ（v）成立，则称f为图G的一个邻点全和可区别非正常k-全染色。图G的邻点全和可区别非正常全染色中最少的颜色数k叫做G的邻点全和可区别全色数，记为fgndi_∑（G）。文章研究了几类笛卡尔乘积图G×H的邻点全和可区别非正常全染色，得到fgndi_∑（P_m×P_n）=fgndi_∑（P_m×C_n）=fgndi_∑（C_m×C_n）=fgndi_∑（P_m×K_n）=fgndi_∑（C_m×K_n）=2。结果表明，邻点全和可区别全染色猜想对上述几类笛卡尔乘积图均成立。

关键词

邻点全和可区别非正常全染色 / 邻点全和可区别全染色数 / 笛卡尔乘积图