Conflict-Free Vertex-Connections of Graphs
| Autor: | Xueliang Li, Yingying Zhang, Haixing Zhao, Stanislav Jendrol, Yaping Mao, Xiaoyu Zhu |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
vertex-coloring Applied Mathematics tree Combinatorics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 05c15 conflict-free vertex-connection QA1-939 Discrete Mathematics and Combinatorics Conflict free 05c40 Mathematics ComputingMethodologies_COMPUTERGRAPHICS MathematicsofComputing_DISCRETEMATHEMATICS 2-connected graph 05c75 |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 40, Iss 1, Pp 51-65 (2020) |
| ISSN: | 2083-5892 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|