Acyclicity in edge-colored graphs

Gregory Gutin*, Mark Jones, Bin Sheng, Magnus Wahlström, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

172 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
JournalDiscrete Mathematics
Volume340
Issue number2
Number of pages8
ISSN0012-365X
DOIs
Publication statusPublished - 2017

Keywords

  • Acyclic
  • Closed trail
  • Closed walk
  • Edge-colored graph
  • Properly colored walk

Fingerprint

Dive into the research topics of 'Acyclicity in edge-colored graphs'. Together they form a unique fingerprint.

Cite this