图的邻点可区分染色猜想成立的两个充分条件

摘要

简单连通图G的邻点可区分全染色(邻强边染色)是图G的一个正常全(边)染色,并且使得任意两个相邻的点u,v满足C(u)≠C(v),其中C(u)={f(u)}U{f(uw)|uw∈(C),w∈V(G)}(C(u)={f(uw)|uw∈E(G),w∈V(G)}).满足图G有一个邻点可区分全染色(邻强边染色)所用的最少颜色数记为Xat(G)(X'as(G)).图G的最大度记为△(G).本文给出了Xat(G)=△(G)+3的一个充分条件和X'as(G)=△(G)+2的一个充分条件.