Geodesic
Conflict-Free Connections of Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 911-920.

Voir la notice de l'article provenant de la source Library of Science

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. In this paper the question for the smallest number of colors needed for a coloring of edges of G in order to make it conflict-free connected is investigated. We show that the answer is easy for 2-edge-connected graphs and very difficult for other connected graphs, including trees.
Keywords: edge-coloring, conflict-free connection, 2-edge-connected graph, tree 
@article{DMGT_2018_38_4_a3,
     author = {Czap, J\'ulius and Jendro\v{l}, Stanislav and Valiska, Juraj},
     title = {Conflict-Free {Connections} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {911--920},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a3/}
}
TY  - JOUR
AU  - Czap, Július
AU  - Jendroľ, Stanislav
AU  - Valiska, Juraj
TI  - Conflict-Free Connections of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 911
EP  - 920
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a3/
LA  - en
ID  - DMGT_2018_38_4_a3
ER  - 
%0 Journal Article
%A Czap, Július
%A Jendroľ, Stanislav
%A Valiska, Juraj
%T Conflict-Free Connections of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 911-920
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a3/
%G en
%F DMGT_2018_38_4_a3
Czap, Július; Jendroľ, Stanislav; Valiska, Juraj. Conflict-Free Connections of Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 911-920. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a3/

[1] S.A. van Aardt, C. Brause, A.P. Burger, M. Frick, A. Kemnitz and I. Schiermeyer, Proper connection and size of graphs, Discrete Math. 340 (2017) 2673–2677. doi:10.1016/j.disc.2016.09.021

[2] E. Andrews, C. Lumduanhom, E. Laforge and P. Zhang, On proper-path colorings in graphs, J. Combin. Math. Combin. Comput. 97 (2016) 189–207.

[3] V. Borozan, S. Fujita, A. Gerek, C. Magnant, Y. Manoussakis, L. Montero and Zs. Tuza, Proper connection of graphs, Discrete Math. 312 (2012) 2550–2560. doi:10.1016/j.disc.2011.09.003

[4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85–98.

[5] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, Sixth Edition (Boca Raton, CRC Press, 2016).

[6] P. Cheilaris, B. Keszegh and D. Pálvöolgyi, Unique-maximum and conflict-free coloring for hypergraphs and tree graphs, SIAM J. Discrete Math. 27 (2013) 1775–1787. doi:10.1137/120880471

[7] P. Cheilaris and G. Tóth, Graph unique-maximum and conflict-free colorings, J. Discrete Algorithms 9 (2011) 241–251. doi:10.1016/j.jda.2011.03.005

[8] I. Fabrici and F. Göring, Unique-maximum coloring of plane graphs, Discuss. Math. Graph Theory 36 (2016) 95–102. doi:10.7151/dmgt.1846

[9] R. Gu, X. Li and Z. Qin, Proper connection number of random graphs, Theoret. Comput. Sci. 609 (2016) 336–343. doi:10.1016/j.tcs.2015.10.017

[10] F. Huang, X. Li and S. Wang, Proper connection number and 2- proper connection number of a graph . arxiv.org/pdf/1507.01426v2.pdf

[11] N. Kamčev, M. Krivelevich and B. Sudakov, Some remarks on rainbow connectivity, J. Graph Theory 83 (2016) 372–383. doi:10.1002/jgt.22003

[12] A. Kemnitz, J. Przybyło, I. Schiermeyer and M. Wózniak, Rainbow connection in sparse graphs, Discuss. Math. Graph Theory 33 (2013) 181–192. doi:10.7151/dmgt.1640

[13] A. Kemnitz and I. Schiermeyer, Graphs with rainbow connection number two, Discuss. Math. Graph Theory 31 (2011) 313–320. doi:10.7151/dmgt.1547

[14] X. Li, M. Liu and I. Schiermeyer, Rainbow connection number of dense graphs, Discuss. Math. Graph Theory 33 (2013) 603–611. doi:10.7151/dmgt.1692

[15] X. Li and C. Magnant, Properly colored notions of connectivity — a dynamic survey, Theory and Applications of Graphs 0, Article 2 (2015). doi:10.20429/tag.2015.000102

[16] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: a survey, Graphs Combin. 29 (2013) 1–38. doi:10.1007/s00373-012-1243-2

[17] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs in Mathematics, Berlin, Springer, 2012).

[18] K. Makino, Y. Uno and T. Ibaraki, On minimum edge ranking spanning trees, J. Algorithms 38 (2001) 411–437. doi:10.1006/jagm.2000.1143

[19] R. Melville and W. Goddard, Coloring graphs to produce properly colored walks, Graphs Combin. 33 (2017) 1271–1281. doi:10.1007/S00373-017-1843-y

[20] J. Pach and G. Tardos, Conflict-free colourings of graphs and hypergraphs, Comb. Probab. Comput. 18 (2009) 819–834. doi:10.1017/S0963548309990290

[21] I. Schiermeyer, Rainbow connection in graphs with minimum degree three, IWOCA 2009, Lecture Notes in Comput. Sci. 5874 (2009) 432–437. doi:10.1007/978-3-642-10217-2_42

[22] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25–30.

[23] D.B. West, Introduction to Graph Theory, Second Edition (New Delhi, Prentice-Hall, 2005).