Back to Search
Start Over
Conflict-free connection number and independence number of a graph
- 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 :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2012.04820
- Document Type :
- Working Paper