Links in edge-colored graphs (Q966157): Difference between revisions

The authors deal with the coloured version of the \(k\)-linked problem in edge-coloured multigraphs. A graph is \(k\)-linked (\(k\geq 1\)) if for each \(k\) pairs of vertices \(x_1,u_1,\dots, x_k,y_k\) there exist \(k\) pairwise vertex disjoint paths, one per each pair \((x_i, y_i)\) (\(i= 1,\dots,k\)). Analogously, a graph is called \(k\)-edge-linked if these \(k\) paths are pairwise edgedisjoint. Conditions for colour degrees, sufficient for the \(k\)-linked (\(k\)-edge-linked) property are given. One of the results obtained in the present paper is a partial answer to an old question posed by one of the authors. Related conjectures are proposed.