Geodesic
Conflict-Free Vertex Connection Number at Most 3 and Size of Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 617-632.

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

A path in a vertex-coloured graph is called conflict-free if there is a colour used on exactly one of its vertices. A vertex-coloured graph is said to be conflict-free vertex-connected if any two distinct vertices of the graph are connected by a conflict-free vertex-path. The conflict-free vertex-connection number, denoted by vcfc(G), is the smallest number of colours needed in order to make G conflict-free vertex-connected. Clearly, vcfc(G) ≥ 2 for every connected graph on n ≥ 2 vertices. Our main result of this paper is the following. Let G be a connected graph of order n. If |E(G)|≥n-62+7, then vcfc(G) ≤ 3. We also show that vcfc(G) ≤ k + 3 − t for every connected graph G with k cut-vertices and t being the maximum number of cut-vertices belonging to a block of G.
Keywords: vertex-colouring, conflict-free vertex-connection number, size of graph 
@article{DMGT_2021_41_2_a16,
     author = {Doan, Trung Duy and Schiermeyer, Ingo},
     title = {Conflict-Free {Vertex} {Connection} {Number} at {Most} 3 and {Size} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {617--632},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a16/}
}
TY  - JOUR
AU  - Doan, Trung Duy
AU  - Schiermeyer, Ingo
TI  - Conflict-Free Vertex Connection Number at Most 3 and Size of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 617
EP  - 632
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a16/
LA  - en
ID  - DMGT_2021_41_2_a16
ER  - 
%0 Journal Article
%A Doan, Trung Duy
%A Schiermeyer, Ingo
%T Conflict-Free Vertex Connection Number at Most 3 and Size of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 617-632
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a16/
%G en
%F DMGT_2021_41_2_a16
Doan, Trung Duy; Schiermeyer, Ingo. Conflict-Free Vertex Connection Number at Most 3 and Size of Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 617-632. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a16/

[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, E. Laforge, C. Lumduanhom 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] H. Chang, T.D. Doan, Z. Huang, S. Jendrol’, X. Li and I. Schiermeyer, Graphs with conflict-free connection number two, Graphs Combin. 34 (2018) 1553–1563. doi:10.1007/s00373-018-1954-0

[5] H. Chang, Z. Huang, X. Li, Y. Mao and H. Zhao, Nordhaus-Gaddum-type theorem for conflict-free connection number of graphs . arXiv:1705.08316v1[math.CO].

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

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

[8] L. Chen, X. Li and Y. Shi, The complexity of determining the rainbow vertex-connection of a graph, Theoret. Comput. Sci. 412 (2011) 4531–4535. doi:10.1016/j.tcs.2011.04.032

[9] E. Chizmar, C. Magnant and P.S. Nowbandegani, Note on vertex and total proper connection numbers, AKCE Int. J. Graphs Comb. 13 (2016) 103–106. doi:10.1016/j.akcej.2016.06.003

[10] J. Czap, S. Jendrol’ and J. Valiska, Conflict-free connections of graphs, Discuss. Math. Graph Theory 38 (2018) 911–920. doi:10.7151/dmgt.2036

[11] S. Jendrol’, X. Li, Y. Mao, Y. Zhang, H. Zhao and X. Zhu, Conflict-free vertexconnections of graphs, Discuss. Math. Graph Theory, in press. doi:10.7151/dmgt.2116

[12] M. Ji, X. Li and X. Zhu, Conflict-free connections: algorithm and complexity, arXiv:1805.08072 (2018).

[13] H. Jiang, X. Li, Y. Zhang and Y. Zhao, On (strong) proper vertex-connection of graphs, Bull. Malays. Math. Sci. Soc. 41 (2018) 415–425. doi:10.1007/s40840-015-0271-5

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

[15] M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185–191. doi:10.1002/jgt.20418

[16] X. Li and S. Liu, Tight upper bound of the rainbow vertex-connection number for 2 -connected graphs, Discrete Appl. Math. 173 (2014) 62–69. doi:10.1016/j.dam.2014.04.002

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

[18] X. Li, Y. Mao and Y. Shi, The strong rainbow vertex-connection of graphs, Util. Math. 93 (2014) 213–223.

[19] X. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory 33 (2013) 307–313. doi:10.7151/dmgt.1664

[20] 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

[21] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer-Verlag, New York, 2012). doi:10.1007/978-1-4614-3119-0

[22] Z. Li and B. Wu, Maximum value of conflict-free vertex-connection number of graphs, Discrete Math. Algorithms Appl. 10 (2018) 1850059. doi:10.1142/S1793830918500593

[23] D.B. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, 2001).