Back to Search Start Over

Conflict-free connection number and independence number of a graph

Authors :
Wang, Jing
Ji, Meng
Publication Year :
2020

Abstract

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)\le \alpha(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 $\Delta(T)\ge \frac{\alpha(T)+2}{2}$, then $cfc(T)=\Delta(T)$.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2012.04820
Document Type :
Working Paper