Acyclicity in edge-colored graphs

DOI10.1016/J.DISC.2016.07.012MaRDI QIDQ2374151zbMATHOpenAlexFDO

Authors Yanyan Li

Publication date 14 December 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.01824

zbMATH Keywords

acyclicclosed trailedge-colored graphclosed walkproperly colored walk

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

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 trails, and PC 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.

Recommendations

• Paths and Trails in Edge-Colored Graphs
• Paths and trails in edge-colored graphs
• On \(s\)--\(t\) paths and trails in edge-colored graphs
• A classification of edge-colored graphs based on properly colored walks
• On paths, trails and closed trails in edge-colored graphs

Cites work

• scientific article; zbMATH DE number 4049453 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A Dirac type condition for properly coloured paths and cycles
• A note on alternating cycles in edge-coloured graphs
• Alternating cycles in edge-partitioned graphs
• An Edge-Colored Version of Dirac's Theorem
• An NP-complete matching problem
• Chinese postman problem on edge-colored multigraphs
• Cycles and paths in edge‐colored graphs with given degrees
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Digraphs
• Graph folding and programmable logic array
• Hamiltonian circuits determining the order of chromosomes
• Parameterized algorithms
• Paths and trails in edge-colored graphs
• Properly colored paths and cycles
• Total Ordering Problem

Cited in

(8)

• A classification of edge-colored graphs based on properly colored walks
• A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs
• Properly coloured cycles and paths: Results and open problems
• Acyclic digraphs
• Acyclic edge coloring of 2-degenerate graphs
• Acyclic edge coloring through the Lovász local lemma
• Odd properly colored cycles in edge-colored graphs
• scientific article; zbMATH DE number 908771 (Why is no real title available?)

This page was built for publication: Acyclicity in edge-colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2374151)