컨텐츠 시작

학술대회/행사

초록검색

제출번호(No.) 0201
분류(Section) Contributed Talk
분과(Session) (DM) Discrete Mathematics (DM)
발표시간(Time) 26th-D-10:10 -- 10:30
영문제목
(Title(Eng.))
Unavoidable butterfly minors in digraphs of large cycle rank
저자(Author(s))
Meike Hatzel2, O-joung Kwon1, Myounghwan Lee1, Sebastian Wiederrecht3
Hanyang University1, IBS-DIMAG2, KAIST3
초록본문(Abstract) Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We prove that for every positive integer $k$, there exists a finite list $(\mathcal{I}_1, \ldots, \mathcal{I}_{g(k)})$ of families of digraphs satisfying that a butterfly minor closed class $\mathcal{C}$ of digraphs has cycle rank at most $k$ if and only if $\mathcal{I}_j\nsubseteq \mathcal{C}$ for all $j\in \{1, \ldots, g(k)\}$. Two families consist of directed ladders and directed cycle chains, while the others have certain tree-like structures.
분류기호
(MSC number(s))
05C75, 05C83
키워드(Keyword(s)) Butterfly-minor, cycle-rank, directed graph, forbidden graph characterization
강연 형태
(Language of Session (Talk))
Korean