Open AccessUpper Boundsand Extreme Results for Conflict-free Vertexconnection Number
Author(s) -
Meng Ji,
Xueliang Li,
Ingo Schiermeyer
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1995/1/012060
Subject(s) - combinatorics , mathematics , vertex (graph theory) , neighbourhood (mathematics) , graph , discrete mathematics , mathematical analysis
A path of a vertex-colored graph is conflict-free path, if there exists a color used only on one of its vertices; a vertex-colored graph is conflict-free vertex-connected, if there is a conflict-free path between each pair of distinct vertices of the graph. For a connected graph G, the minimum number of colors required to make G conflict-free vertex-connected is conflict-free vertex- connection number of G, denoted by vcfc(G). In this paper, we first showed an upper bound of vcfc(G) for the general graph by structural method. And then, we gave a partial solution to the conjecture on the conflict-free vertex-connection number by contradiction, posed by Doan and Schiermeyer in [Conflict-free vertex connection number at most 3 and size of graphs, Discus. Math. Graph Theory].