Reachability problems in edge-colored digraphs
type: Item
instance of: scholarly article
title: Reachability problems in edge-colored digraphs
zbMATH Open document ID: 1127.05049
author: Peter Arpin
author: Vaclav Linek
published in: Discrete Mathematics
publication date: 2007-08-23T00:00:00Z
review text: Let \(G\) be a multidigraph whose arcs are colored with the vertices of a digraph \(D\). A walk \(W\) in \(G\) is a \(D\)-walk if the consecutive colors encountered on \(W\) form a walk in \(D\). A set \(S\) of vertices of \(G\) is a \(D\)-sink if every vertex not in \(S\) can reach some vertex in \(S\) via a \(D\)-walk. Let \(B_1,B_2\), and \(B_3\) denote the set of digraphs \(D\) such that every finite \(D\)-arc-colored multidigraph \(G\) has a \(D\)-sink \(S\) such that (1) \(|S|=1\), or (2) no two vertices of \(S\) are joined by an arc, or (3) no two vertices of \(S\) have a \(D\)-walk between them, respectively. The authors characterize the set \(B_2\) and show that \(B_1\subset B_2\subset B_3\), where the inclusions are strict, among other things.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5182390
zbMATH Keywords: tournament
zbMATH Keywords: edge colored digraph
zbMATH Keywords: monochromatic path
zbMATH Keywords: reachability problems
zbMATH Keywords: kernel
reviewed by: J. W. Moon
MaRDI profile type: MaRDI publication profile
full work available at URL: j.disc.2006.09.042
OpenAlex ID: W2005620597
cites work: Q4539516
cites work: On Ramsey-Turán type problems in tournaments
cites work: Q5422499
cites work: Q4050630
cites work: On monochromatic paths and monochromatic cycles in edge coloured tournaments
cites work: A counterexample to a conjecture on edge-coloured tournaments
cites work: Absorbing sets in arc-coloured tournaments
cites work: Q4388214
cites work: Rooted spanning trees in tournaments
cites work: On monochromatic paths in m-coloured tournaments
cites work: Q5585195
cites work: Q4756732
cites work: Q3220616
cites work: Monotone reachability in arc-colored tournaments
cites work: On monochromatic paths in edge-coloured digraphs
cites work: Q5837980
DOI: 10.1016/J.DISC.2006.09.042
Recommended article: Reachability Problems on Directed Graphs
Recommended article: Edge-Coloring Problems for Graphs.
Recommended article: Reachability relations in digraphs
Recommended article: On resolving edge colorings in graphs
Recommended article: Planar and grid graph reachability problems
Recommended article: NP-completeness of edge-colouring some restricted graphs
Recommended article: On connectivities of edge-colored graphs
Recommended article: Reachability problems in interval-constrained and cardinality-constrained graphs
Recommended article: A generalization of edge-coloring in graphs
Recommended article: Q4014299
description: scientific article; zbMATH DE number 5182390