Gutin, Gregory; Jones, Mark; Sheng, Bin; Wahlström, Magnus; Yeo, Anders Acyclicity in edge-colored graphs. (English) Zbl 1351.05075 Discrete Math. 340, No. 2, 1-8 (2017). Summary: 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. Cited in 4 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles Keywords:edge-colored graph; properly colored walk; closed walk; closed trail; acyclic PDFBibTeX XMLCite \textit{G. Gutin} et al., Discrete Math. 340, No. 2, 1--8 (2017; Zbl 1351.05075) Full Text: DOI arXiv References: [1] Abouelaoualim, A.; Das, K. Ch.; Faria, L.; Manoussakis, Y.; Martinhon, C.; Saad, R., Paths and trails in edge-colored graphs, Theoret. Comput. Sci., 409, 497-510 (2008) · Zbl 1155.68053 [2] Abouelaoualim, A.; Das, K. Ch.; Fernandez de la Vega, W.; Karpinski, M.; Manoussakis, Y.; Martinhon, C. A.; Saad, R., Cycles and paths in edge-colored graphs with given degrees, J. Graph Theory, 64, 1, 63-86 (2010) · Zbl 1202.05067 [3] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2009), Springer-Verlag: Springer-Verlag London · Zbl 1170.05002 [4] Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001 [5] Dorniger, D., On permutations of chromosomes, Contrib. General Algebra, 5, 95-103 (1987) [6] Dorniger, D., Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math., 50, 159-168 (1994) · Zbl 0823.92010 [7] Dorniger, D.; Timischl, W., Geometrical constraints on Bennett’s predictions of chromosome order, Heredity, 58, 321-325 (1987) [8] Downey, R. G.; Fellows, M. R., Foundations of Parameterized Complexity (2013), Springer · Zbl 0914.68076 [9] Fujita, S.; Magnant, C., Properly colored paths and cycles, Discrete Appl. Math., 159, 14, 1391-1397 (2011) · Zbl 1228.05150 [10] Grossman, J. W.; Haggkvist, R., Alternating cycles in edge-partitioned graphs, J. Combin. Theory Ser. B, 34, 77-81 (1983) · Zbl 0491.05039 [12] Hu, T. C.; Kuo, Y. S., Graph folding and programmable logical arrays, Networks, 17, 19-37 (1987) · Zbl 0649.05038 [14] Lo, A., A dirac type condition for properly colored paths and cycles, J. Graph Theory, 76, 60-87 (2014) · Zbl 1294.05077 [15] Lo, A., An edge-colored version of Dirac’s theorem, SIAM J. Discrete Math., 28, 1, 18-36 (2014) · Zbl 1297.05085 [16] Opatrný, J., Total ordering problem, SIAM J. Comput., 8, 1, 111-114 (1979) · Zbl 0395.68065 [17] Pevzner, P. A., DNA physical mapping and properly edge-colored Eulerian cycles in colored graphs, Algorithmica, 13, 77-105 (1995) · Zbl 0840.92011 [18] Plaisted, D. A.; Zaks, S., An NP-complete matching problem, Discrete Appl. Math., 2, 1, 65-72 (1980) · Zbl 0489.68064 [19] Yeo, A., A note on alternating cycles in edge-colored graphs, J. Combin. Theory Ser. B, 69, 222-225 (1997) · Zbl 0870.05042 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.