컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0546 |
|---|---|
| 분류(Section) | Contributed Talk |
| 분과(Session) | Combinatorics / Graph Theory / Cryptography / Coding Theory (SS-05) |
| 영문제목 (Title(Eng.)) |
Excluded vertex-minors for graphs of linear rank-width at most $k$ |
| 저자(Author(s)) |
Jisu Jeong1, O-joung Kwon1, Sang-il Oum1 KAIST1 |
| 초록본문(Abstract) | Linear rank-width is a graph width parameter, which is a variation of rank-width by restricting its tree to a caterpillar. As a corollary of known theorems, for each $k$, there is a finite set $\mathcal{O}_k$ of graphs such that a graph $G$ has linear rank-width at most $k$ if and only if no vertex-minor of $G$ is isomorphic to a graph in $\mathcal{O}_k$. However, no attempts have been made to bound the number of graphs in $\mathcal{O}_k$ for $k\ge 2$. We construct, for each $k$, $2^{\Omega(3^k)}$ pairwise locally non-equivalent graphs that are excluded vertex-minors for graphs of linear rank-width at most $k$. Therefore the number of graphs in $\mathcal{O}_k$ is at least double exponential. |
| 분류기호 (MSC number(s)) |
05C75 |
| 키워드(Keyword(s)) | rank-width, linear rank-width, vertex-minor, well-quasi-ordering |
| 강연 형태 (Language of Session (Talk)) |
English |