Time: 9h30, Thursday, June 25, 2020

Location: Room 612, Building A6, Institute of Mathematics

Abstract: A path in a vertex-coloured graph is called emph{conflict-free} if there is a colour used on exactly one of its vertices. A vertex-coloured graph is said to be emph{conflict-free vertex-connected} if any two distinct vertices of the graph are connected by a conflict-free vertex-path. The emph{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) geq 2$ for every connected graph on $n geq 2$ vertices.Our main result of this paper is the following: Let $G$ be a connected graph of order $n$. If $|E(G)|geq{n-6choose 2} +7$, then $vcfc(G)leq3$. We also show that $vcfc(G)leq 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.$.