Conflict-Free Connections of Graphs

Discussiones Mathematicae Graph Theory

卷:38

Czap Július¹  Jendroľ Stanislav²  Valiska Juraj² 

[1] Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Košice, Němcovej 32, 040 01Košice, Slovakia;

[2] Institute of Mathematics, P.J. Šafarik University, Jesenna 5, 040 01Košice, Slovakia;

关键词: edge-coloring;    conflict-free connection;    2-edge-connected graph;    tree;    05c15;   

DOI  :  10.7151/dmgt.2036

来源: DOAJ

【 摘 要 】

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. In this paper the question for the smallest number of colors needed for a coloring of edges of G in order to make it conflict-free connected is investigated. We show that the answer is easy for 2-edge-connected graphs and very difficult for other connected graphs, including trees.

【 授权许可】

Unknown