pith. machine review for the scientific record. sign in

arxiv: 1705.07270 · v1 · pith:TCPGAHTYnew · submitted 2017-05-20 · 🧮 math.CO

Conflict-free vertex-connections of graphs

classification 🧮 math.CO
keywords conflict-freeconnectedgraphgraphsemphpathvertex-coloredvertex-connected
0
0 comments X
read the original abstract

A path in a vertex-colored graph is called \emph{conflict free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be \emph{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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.