论文标题
无冲突连接编号和图的独立数
Conflict-free connection number and independence number of a graph
论文作者
论文摘要
如果其两个顶点通过路径连接，则边缘颜色的图形$ g $是无冲突连接的，该路径包含恰好在其边缘之一上使用的颜色。由$ cfc（g）$表示的连接图$ g $的无冲突连接编号定义为为了使$ g $无冲突连接所需的最小颜色数。在本文中，我们研究了图形的无冲突连接编号与独立数之间的关系。我们首先表明，任何连接的图形$ g $ $ cfc（g）\leα（g）$，并给出一个示例，显示界限是锋利的。通过此结果，我们证明，如果$ t $是$δ（t）\ ge \ frac {α（t）+2} {2} $的树，则$ cfc（t）=δ（t）$。
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 α(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)\ge \frac{α(T)+2}{2}$, then $cfc(T)=Δ(T)$.
