图在约束条件下的邻点可区别全染色

崔福祥,杨 超,叶宏波

PDF(1266 KB)
PDF(1266 KB)
广州大学学报(自然科学版) ›› 2020, Vol. 19 ›› Issue (1) : 50-54.
论文

图在约束条件下的邻点可区别全染色

  • 崔福祥,杨 超,叶宏波
作者信息 +

Adjacent vertex-distinguishing total colorings of graphs with constraint conditions

  • CUi Fu-xiang,YANG Chao、YE Hong-bo
Author information +
History +

摘要

设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈N(u)},eC[f,u]=C(f,u)∪{f(u)},C[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}.N(u)表示顶点u的邻集,N(u)2e表示与顶点u的相关联的边集合.令C[f;x]={C(f,x);C[f,x];C[f,x]},对任意的边xy∈E(G),C[f;x]2≠C[f;y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C[f,x]≠C[f,y]同时成立.对任意的边xy∈E(G),22如果有C[f;x]≠C[f;y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为k-(3)-AVDTC).图G的(3)-邻点可区别全染色中所需最少的颜色数叫做G的(3)-邻点可区别全色数,记为″(G).文章研究(2,(3)as2)-递归极大平面图的(3)-邻点可区别全染色,并确定此类图的(3)-邻点可区别全色数.此外,提出了简单图的(3)-邻点可区别全染色猜想.

Abstract

Letf: V(G)UE(G)-→{1,2,-,k} be a proper k-total coloring of a simple graph G. Set C(f,u) = {f(e): e∈N.(u)}, C[f,u] =C(f,u)∪{f(u)}, G2[f,u]=C(f,u)∪{f(x): x∈N(u)}∪{f(u)}. Sup- pose C[f; x]= C(f, x);C[f, x];C2[f, x]}. For each edge ry∈E(G) ,C[f;x]≠C[f;y] denotes C(f,x) ≠C(f,y) ,C[f,x]≠C[f,y],C2[f,x]≠C[f,y] holding at the same time. We callf to be a k-(3)-adjacent vertex distinguishing total coloring (k-(3)-AVDTC for short) of G if C[f;x]≠C[f;y] for each edge xy∈ E(G). The minimum number of k colors required for which G admits ak-(3)-AVDTC is denoted by x"3)w(G), and called the (3)-AVDTC chromatic number of G. In this paper, we investigate (3 )-adjacent vertex distin- guishing total coloring of(2 ,2 )-recursive maximal planar graphs and their ( 3)-AVDTC chromatic numbers are determined. Moreover, we propose a conjecture on (3 ) -adjacent vertex distinguishing total colorings of simple graphs.

关键词

全染色 / 点可区别全染色 / (3)-邻点可区别全染色 / 极大平面图

Key words

total coloring / vertex distinguishing total colorings / (3)-adjacent vertex distinguishing total color- ings / maximal planar graphs

引用本文

导出引用
崔福祥,杨 超,叶宏波. 图在约束条件下的邻点可区别全染色. 广州大学学报(自然科学版). 2020, 19(1): 50-54
CUi Fu-xiang,YANG Chao、YE Hong-bo. Adjacent vertex-distinguishing total colorings of graphs with constraint conditions. Journal of Guangzhou University(Natural Science Edition). 2020, 19(1): 50-54

参考文献

[1] VizingVG.Onanestimateofthechromaticclassofapgraph[J].DiskretAnaliz,1964,3(1):2530. [2] BehzadM.Graphsandtheirchromaticnumbers[D].EastLansing:MichiganStateUniversity,1965
PDF(1266 KB)

111

Accesses

0

Citation

Detail

段落导航
相关文章

/