2017/05/20 by Li, Xueliang, Zhang, Yingying, Zhu, Xiaoyu +2 · 1 citation
#05C15 #05C40 #05C75 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1705.07270
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.