Acyclicity in edge-colored graphs. / Gutin, Gregory; Jones, Mark; Sheng, Bin; Wahlstrom, Magnus; Yeo, Anders.

In: Discrete Mathematics, Vol. 340, No. 2, 06.02.2017, p. 1-8.

Research output: Contribution to journalArticlepeer-review





A walk W in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in W is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type i is a proper superset of graphs of acyclicity of type i+1, i=1,2,3,4. The first three types are equivalent to the absence of PC cycles, PC closed trails, and PC closed walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex-disjoint PC paths between two vertices and the minimum number of vertices to meet all PC paths between two vertices.
Original languageEnglish
Pages (from-to)1-8
Number of pages8
JournalDiscrete Mathematics
Issue number2
Early online date30 Aug 2016
Publication statusPublished - 6 Feb 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26852833