Conflict-free connection of trees. (arXiv:1712.10010v1 [math.CO])

An edge-colored graph $G$ is \emph{conflict-free connected} if, between each pair of distinct vertices, there exists a path containing a color used on exactly one of its edges. The \emph{conflict-free connection number} of a connected graph $G$, denoted by $cfc(G)$, is defined as the smallest number of colors that are required in order to make $G$ conflict-free connected. A coloring of vertices of a hypergraph $H=(\mathcal{V},\mathcal{E})$ is called \emph{conflict-free} if each hyperedge $e$ of $H$ has a vertex of unique color that does not get repeated in $e$. The smallest number of colors required for such a coloring is called the \emph{conflict-free chromatic number} of $H$, and is denoted by \emph{$\chi_{cf}(H)$}. In this paper, we study the conflict-free connection coloring of trees, which is also the conflict-free coloring of edge-path hypergraphs of trees. We first prove that for a tree $T$ of order $n$, $cfc(T)\geq cfc(P_n)=\lceil \log_{2} n\rceil$, and this completely confirms 查看全文>>