Acyclicity in edge-colored graphs

DOI10.1016/J.DISC.2016.07.012zbMATH Open1351.05075arXiv1601.01824OpenAlexW2963476366MaRDI QIDQ2374151FDOQ2374151

Yanyan Li

Publication date: 14 December 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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)

Cites Work

• Parameterized Algorithms
• Digraphs
• Title not available (Why is that?)
• Total Ordering Problem
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Alternating cycles in edge-partitioned graphs
• A note on alternating cycles in edge-coloured graphs
• Cycles and paths in edge‐colored graphs with given degrees
• Graph folding and programmable logic array
• Properly colored paths and cycles
• Paths and trails in edge-colored graphs
• An Edge-Colored Version of Dirac's Theorem
• A Dirac Type Condition for Properly Coloured Paths and Cycles
• Chinese postman problem on edge-colored multigraphs
• Hamiltonian circuits determining the order of chromosomes
• Title not available (Why is that?)
• An NP-complete matching problem

Cited In (7)

• A classification of edge-colored graphs based on properly colored walks
• Acyclic edge coloring through the Lovász local lemma
• Title not available (Why is that?)
• Acyclic Digraphs
• Acyclic edge coloring of 2-degenerate graphs
• Odd properly colored cycles in edge-colored graphs
• A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs

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)