Graphs with Conflict-Free Connection Number Two

• Published in: Graphs and combinatorics 2018-11, Vol.34 (6), p.1553-1563
• Main Authors: Chang, Hong, Doan, Trung Duy, Huang, Zhong, Jendrol’, Stanislav, Li, Xueliang, Schiermeyer, Ingo
• Format: Article
• Language: English
• Subjects: Apexes; Combinatorics; Completeness; Decision trees; Engineering Design; Forests; Graph coloring; Graph theory; Mathematics; Mathematics and Statistics; Original Paper
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-018-1954-0

An edge-colored graph G is conflict-free connected if every 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 the smallest number of colors needed in order to make G conflict-free connected. For a graph G ,  let C ( G ) be the subgraph of G induced by its set of cut-edges. In this paper, we first show that, if G is a connected non-complete graph G of order n ≥ 9 with C ( G ) being a linear forest and with the minimum degree δ ( G ) ≥ max { 3 , n - 4 5 } , then c f c ( G ) = 2 . The bound on the minimum degree is best possible. Next, we prove that, if G is a connected non-complete graph of order n ≥ 33 with C ( G ) being a linear forest and with d ( x ) + d ( y ) ≥ 2 n - 9 5 for each pair of two nonadjacent vertices x ,  y of V ( G ), then c f c ( G ) = 2 . Both bounds, on the order n and the degree sum, are tight. Moreover, we prove several results concerning relations between degree conditions on G and the number of cut edges in G .