On the maximum value of conflict-free verex-connection number of graphs

Abstract

A path in a vertex-colored graph is called {\it conflict-free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be {\it conflict-free vertex-connected} if any two vertices of the graph are connected by a conflict-free path. The {\it conflict-free vertex-connection number}, denoted by $vcfc(G)$, is defined as the smallest number of colors required to make $G$ conflict-free vertex-connected. Li et al. conjectured that for a connected graph $G$ of order $n$, $vcfc(G)\le vcfc(P_n)$. We confirm that the conjecture is true and pose a a relevant conjecture concerning the conflict-free connection number introduced by Czap et al..

5 pages

References in corpus (3)

• Nordhaus-Gaddum-type theorem for conflict-free connection number of graphs
• Conflict-free vertex-connections of graphs
• Conflict-free connection numbers of line graphs

Cited by in corpus (3)

• Conflict-free (vertex)-connection numbers of graphs with small diameters
• Strong conflict-free connection of graphs
• Conflict-free connection number and independence number of a graph