Conflict-free Connection Number and Independence Number of a Graph

• 作者: Jing WANG Meng JI
• 来源期刊: 应用数学学报（英文版）
• 年，卷（期）: 2021,（2）
• 页码范围: 278-286
• 页数: 9页
• 语种: 英文

摘要

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 cfc(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 numberand the independence number of a graph.We firstly show that cfc(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 cfc(T) =△(T).