Pavol Jozef Šafárik University in Kosice - Faculty of Science


Institute of Mathematics

The graph theorists of Institute of Mathematics published, in cooperation with Technical University of Košice, the paper doi:10.7151/dmgt.2036 in quality Current Content-based journal Discussiones Mathematicae Graph Theory in which (motivated by similar previously known concepts of colourings which use the chromatic connectedness between vertices) they defined and described properties of a new edge colouring, so called conflict-free connection where every two vertices of a graph are connected by a path with the single occurrence of some colour. In their work, it was showed that determining the minimum number of colours used in conflict-free connection is easy for edge-2-connected graphs, but hard for graphs with cut-edges (for which they derived some necessary and some sufficient conditions for conflict-free 2-colourability); along with these results, there were studied the estimates of this chromatic invariant as well as the proper version of such edge colouring.

Last update: 06.02.2019