图的最小度和无矛盾连通数

作者：严政; 赵小鹏; 慈永鑫

来源：长江大学学报(自然科学版), 2022, 19(02): 113-118.

DOI：10.16772/j.cnki.1673-1409.20220112.002

• 连通图
• 最小度
• 边无矛盾染色
• 割边
• 无矛盾连通数

边染色图中如果一条路径至少有一种颜色仅出现一次，则称为无矛盾路径；如果任意2个不同顶点之间都存在1条无矛盾路径，则称为无矛盾连通图。图中无矛盾连通所需要的最小颜色数称为图的无矛盾连通数。结合具有割边的图和星图的结构特点，探讨了图中关于最小度的无矛盾染色，采用构造法和删除割边法，给出了满足一些最小度、阶和边数条件的图的无矛盾连通数上界。结果表明，满足阶小于ks+2s+3k+6(s≥k≥2)的连通图G，如果最小度δ(G)≥s+2，其无矛盾连通数cfc(G)≤k;2-连通图Cn(n≥3)的t-冠(t≥2)的无矛盾连通数■；对于阶为n最小度为δ的连通图G，如果边数大于■其无矛盾连通数cfc(G)≤k。

• 单位
  数学学院