Conflict-free Connection Number and Independence Number of a Graph  

作　　者：Jing WANG Meng JI 

机构地区：[1]School of Computer Engineering and Applied Mathematics,Changsha University,Changsha 410022,China [2]Hunan Province Key Laboratory of Industrial Internet Technology and Security,Changsha University,Chang-sha 410022,China [3]College of Mathematical Science,Tianjin Normal University,Tianjin 300007,China

出　　处：《Acta Mathematicae Applicatae Sinica》2021年第2期278-286,共9页应用数学学报（英文版）

基　　金：supported by Hunan Education Department Foundation(No.18A382)。

摘　　要：An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf c(G),is defined as the minimum number of colors that are required in order to make G conflict-free connected.In this paper,we investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).

关 键 词：EDGE-COLORING conflict-free connection number independence number TREE 

分 类 号：O157.5[理学—数学]