Abstract
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\ge 9\) with C(G) being a linear forest and with the minimum degree \(\delta (G)\ge \max \{3, \frac{n-4}{5}\}\), then \(cfc(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\ge 33\) with C(G) being a linear forest and with \(d(x)+d(y)\ge \frac{2n-9}{5}\) for each pair of two nonadjacent vertices x, y of V(G), then \(cfc(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.
Similar content being viewed by others
References
Andrews, E., Laforge, E., Lumduanhom, C., Zhang, P.: On proper-path colorings in graphs. J. Comb. Math. Comb. Comput. 97, 189–207 (2016)
van Aardt, S.A., Brause, C., Burger, A.P., Frick, M., Kemnitz, A., Schiermeyer, I.: Proper connection and size of graphs. Discrete Math. 340(11), 2673–2677 (2017)
Bondy, J.A., Murty, U.S.R.: Graph Theory, GTM 244. Springer, New York (2008)
Borozan, V., Fujita, S., Gerek, A., Magnant, C., Manoussakis, Y., Montero, L., Tuza, Z.: Proper connection of graphs. Discrete Math. 312, 2550–2560 (2012)
Brause, C., Duy Doan, T., Schiermeyer, I.: Minimum degree conditions for the proper connection number of graphs. Graphs Comb. 33, 833–843 (2017)
Chang, H., Huang, Z., Li, X., Mao, Y., Zhao, H.: Nordhaus–Gaddum-type theorem for conflict-free connection number of graphs. arXiv:1705.08316 [math.CO]
Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133, 85–98 (2008)
Czap, J., Jendrol’, S., Valiska, J.: Conflict-free connection of graphs. Discuss. Math. Graph Theory 38, 911–920 (2018)
Cheilaris, P., Keszegh, B., Pálvölgyi, D.: Unique-maximum and conflict-free coloring for hypergraphs and tree graphs. SIAM J. Discrete Math. 27, 1775–1787 (2013)
Cheilaris, P., Tóth, G.: Graph unique-maximum and conflict-free colorings. J. Discrete Algorithms 9, 241–251 (2011)
Deng, B., Li, W., Li, X., Mao, Y., Zhao, H.: Conflict-free connection numbers of line graphs, graphs. Lect. Notes Comput. Sci. No.10627, 141–151 (2017)
Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free coloring of simple geometic regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33, 94–136 (2003)
Gu, R., Li, X., Qin, Z.: Proper connection number of random graphs. Theor. Comput. Sci. 609(2), 336–343 (2016)
Huang, F., Li, X., Qin, Z., Magnant, C.: Minimum degree condition for proper connection number 2. Theor. Comput. Sci. https://doi.org/10.1016/j.tcs.2016.04.042 (in press)
Laforge, E., Lumduanhom, C., Zhang, P.: Characterizations of graphs having large proper connection numbers. Discuss. Math. Graph Theory 36(2), 439–453 (2016)
Li, X., Magnant, C.: Properly colored notions of connectivity–a dynamic survey. Theory Appl. Graphs. (1) (2015). https://doi.org/10.20429/tag.2015.000102 (Art. 2)
Li, X., Shi, Y., Sun, Y.: Rainbow connections of graphs: A survey. Graphs Comb. 29, 1–38 (2013)
Li, X., Sun, Y.: Rainbow Connections of Graphs. Springer Briefs in Math, Springer, New York (2012)
Li, X., Sun, Y.: An updated survey on rainbow connections of graphs–a dynamic survey. Theory Appl. Graphs (1) (2017). https://doi.org/10.20429/tag.2017.000103 (Art.3)
Pach, J., Tardos, G.: Conflict-free colourings of graphs and hypergraphs. Comb. Probab. Comput. 18, 819–834 (2009)
Acknowledgements
We thank the two reviewers for their helpful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Hong Chang: Supported by NSFC Nos. 11871034 and 11531011.
Trung Duy Doan: Financial support by the Free State of Saxony (Landesstipendium) is thankfully acknowledged by the second author. Supported also by “The National Foundation of Science and Technology Department (NAFOSTED) of Vietnam with project code 101.99-2016.20”.
Stanislav Jendrol’: The work of the fourth author was supported by the Slovak Research and Development Agency under the contract No. APVV-15-0116 and by the Slovak VEGA Grant 1/0368/16.
Ingo Schiermeyer: Part of this research was done while the sixth author was visiting the Center for Combinatorics. Financial support is gratefully acknowledged.
Rights and permissions
About this article
Cite this article
Chang, H., Doan, T.D., Huang, Z. et al. Graphs with Conflict-Free Connection Number Two. Graphs and Combinatorics 34, 1553–1563 (2018). https://doi.org/10.1007/s00373-018-1954-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-018-1954-0