Conflict-free connection of trees

Hong Chang (), Meng Ji (), Xueliang Li () and Jingshu Zhang ()
Additional contact information
Hong Chang: Nankai University
Meng Ji: Nankai University
Xueliang Li: Nankai University
Jingshu Zhang: Nankai University

Journal of Combinatorial Optimization, 2021, vol. 42, issue 3, No 2, 340-353

Abstract: Abstract 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)\ge cfc (P_n)=\lceil \log _{2} n\rceil $$ c f c ( T ) ≥ c f c ( P n ) = ⌈ log 2 n ⌉ , which completely confirms the conjecture of Li and Wu [24]. 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 $$2^{k-1}$$ 2 k - 1 vertices is $$k-1$$ k - 1 . At last, we study trees which are $$ cfc $$ cfc -critical, and prove that if a tree T is $$ cfc $$ cfc -critical, then the conflict-free connection coloring of T is equivalent to the edge ranking of T.

Keywords: Tree; Conflict-free connection coloring; Conflict-free coloring; $$ cfc $$ cfc -critical; Edge ranking; 05C15; 05C40; 05C75; 05C85 (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0363-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:42:y:2021:i:3:d:10.1007_s10878-018-0363-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0363-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().