若干图的倍图的邻点可区别边（全）染色

作者：何雪 田双亮倍图邻点可区别边染色邻点可区别全染色

摘要：设 Ｇ是具有顶点集 Ｖ（Ｇ）和边集 Ｅ（Ｇ）的简单图。如果 Ｇ的一正常边染色 σ满足对任意 ｕｖ∈Ｅ（Ｇ），有Ｃσ（ｕ）≠Ｃσ（ｖ），其中 Ｃσ（ｕ）为点 ｕ的关联边所染颜色构成的集合，则称 σ为 Ｇ的邻点可区别边染色。如果 Ｇ的一正常全染色 σ满足对任意 ｕｖ∈Ｅ（Ｇ），有 Ｓσ（ｕ）≠Ｓσ（ｖ），其中 Ｓσ（ｕ）表示点 ｕ及 ｕ的关联边所染颜色构成的集合，则称 σ为 Ｇ的邻点可区别全染色。图 Ｇ的邻点可区别边（或全）染色所需的最少的颜色数，称为 Ｇ的邻点可区别边（或全）色数，并记为χ′ａｓ（Ｇ）（或 χａｔ（Ｇ））。给出了图 Ｇ的倍图 Ｄ（Ｇ）的以上两个参数的上界，并对完全图与树，确定了它们的倍图的邻点可区别边色数与全色数的精确值.

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社