컨텐츠 시작
학술대회/행사
초록검색
제출번호(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 |