Conflict-free vertex connection number at most 3 and size of graphs
Trung Duy Doan, Ingo Schiermeyer · Discussiones Mathematicae Graph Theory · 2019
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 vcf c(G), is the smallest number of colours needed in order to make G conflict-free vertex-connected. Clearly, vcf c(G) 2 for every connected graph on n 2 vertices.