Unavoidable butterfly minors in digraphs of large cycle rank
By: Meike Hatzel , O-joung Kwon , Myounghwan Lee and more
Potential Business Impact:
Finds patterns in connected paths to understand complex networks.
Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We show that there exists a function $f:\mathbb{N}\to \mathbb{N}$ such that every digraph of cycle rank at least $f(k)$ contains a directed cycle chain, a directed ladder, or a directed tree chain of order $k$ as a butterfly minor. We also investigate a new connection between cycle rank and a directed analogue of the weak coloring number of graphs.
Similar Papers
Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
Combinatorics
Finds patterns in networks to simplify complex problems.
Basis Number of Graphs Excluding Minors
Combinatorics
Finds simpler ways to draw complex maps.
Oriented discrepancy of Hamilton cycles and paths in digraphs
Combinatorics
Finds best paths in computer networks.