Acyclicity in edge-colored graphs

Gregory Gutin, Mark Jones, Bin Sheng, Magnus Wahlstrom, Anders Yeo

Research output: Contribution to journalArticlepeer-review

75 Downloads (Pure)

Abstract

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
Volume340
Issue number2
Early online date30 Aug 2016
DOIs
Publication statusPublished - 6 Feb 2017

Cite this