Authors:
S. Jendrol', X. Li, Y. Mao, Y. Zhang, H. Zhao, X. Zhu
Title:
Conflict-free vertex-connections of graphs
Source:
Discussiones Mathematicae Graph Theory
Received 22.05.2017, Revised 18.01.2018, Accepted 22.01.2018, doi: 10.7151/dmgt.2116

Abstract:
A path in a vertex-colored graph is called conflict-free if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be conflict-free vertex-connected if any two vertices of the graph are connected by a conflict-free path. This paper investigates the question: for a connected graph G, what is the smallest number of colors needed in a vertex-coloring of G in order to make G conflict-free vertex-connected. As a result, we get that the answer is easy for 2-connected graphs, and very difficult for connected graphs with more cut-vertices, including trees.
Keywords:
vertex-coloring, conflict-free vertex-connection, 2-connected
graph, tree

Links:
PDF