2017/12/25 by Hong Chang, Meng Ji, Chang, Hong +5
Computer Science · Mathematics · #05C15 #05C40 #05C75 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #cs.DM #math.CO #msc:05C15 #msc:05C40 #msc:05C75 #msc:05C85
paper · pdf · doi:10.48550/arxiv.1712.10010
16 pages. arXiv admin note: text overlap with arXiv:1002.4210, arXiv:0912.3004 by other authors
openalex publication_date 2017/12/25 · arxiv created 2018/05/17 · arxiv updated 2018/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the conflict-free connection coloring of trees, which is also the conflict-free coloring of the so-called edge-path hypergraphs of trees. We first prove that for a tree T of order n, cfc(T)≥ cfc(Pn)=\lceil log2 n\rceil, which completely confirms the conjecture of Li and Wu. We then present a sharp upper bound for the conflict-free connection number of trees by a simple algorithm. Furthermore, we show that the conflict-free connection number of the binomial tree with 2k-1 vertices is k-1. At last, we study trees which are cfc-critical, and prove that if a tree T is cfc-critical, then the conflict-free connection coloring of T is equivalent to the edge ranking of T.