2020/12/09 by Jing Wang, Wang, Jing, Meng Ji +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2012.04820
openalex publication_date 2020/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 number and the independence number of a graph. We firstly show that cfc(G)≤ α(G) for any connected graph G, and an example is given showing 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).