摘要
边染色图中如果一条路径至少有一种颜色仅出现一次,则称为无矛盾路径;如果任意2个不同顶点之间都存在1条无矛盾路径,则称为无矛盾连通图。图中无矛盾连通所需要的最小颜色数称为图的无矛盾连通数。结合具有割边的图和星图的结构特点,探讨了图中关于最小度的无矛盾染色,采用构造法和删除割边法,给出了满足一些最小度、阶和边数条件的图的无矛盾连通数上界。结果表明,满足阶小于ks+2s+3k+6(s≥k≥2)的连通图G,如果最小度δ(G)≥s+2,其无矛盾连通数cfc(G)≤k;2-连通图Cn(n≥3)的t-冠(t≥2)的无矛盾连通数cfc(G)=3,t=2t,t≥3;对于阶为n最小度为δ的连通图G,如果边数大于n-m-(k+1-m)(δ+1)2+(k+1-m)δ+12+k+1,m=k+1,δ=1kδ-1,δ≥2,其无矛盾连通数cfc(G)≤k。
A path in an edge-colored graph is called conflict-free path if at least one color appears only once.An edge-colored graph is called conflict-free connected graph if there is a conflict-free path between each pair of distinct vertices.The conflict-free connection number of graphs is defined as the smallest number of colors that are required for conflict-free connedtion.In this paper,the problem of conflict-free coloring on the minimum degree of graph was studied by combining the structural characteristics of graphs with cut-edges and the star graph.The minimum degree of graphs conflict-free coloring was discussed by using the construction method and delete cut-edges method.The upper bound of conflict-free connected number of graphs with restrictions on minimum degree,order and size was given.The results show that for connected graphs of order less than ks+2s+3k+6(s≥k≥2),if the minimum degree is greater than s+1,the number of conflict-free connected graphs does not exceed k;for a special 2-connected graph Cn(n≥3),when G is its t-corona(t≥2),the conflict-free connection number cfc(G)=3,t=2t,t≥3;and for connected graphs of order n and minimum degreeδ,if the number of edges is greater than n-m-(k+1-m)(δ+1)2+(k+1-m)δ+12+k+1,m=k+1,δ=1kδ-1,δ≥2,the number of conflict-free connected graphs is not greater than k.
作者
严政
赵小鹏
慈永鑫
YAN Zheng;ZHAO Xiaopeng;CI Yongxin(School of Information and Mathematics,Yangtze University,Jingzhou 434023,Hubei)
出处
《长江大学学报（自然科学版）》
2022年第2期113-118,共6页
Journal of Yangtze University(Natural Science Edition)
基金
国家自然科学基金项目“图的参数与支撑树的研究”(11601041)
湖北省教育厅科学技术研究项目“具有特定性质的生成树的研究”(D20191303)。
关键词
连通图
最小度
边无矛盾染色
割边
无矛盾连通数
connected graph
minimum degree
edge conflict-free coloring
cut-edges
conflict-free connection number
