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/