컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0502 |
|---|---|
| 분류(Section) | Invited Talk |
| 분과(Session) | Combinatorics / Graph Theory / Cryptography / Coding Theory (SS-05) |
| 영문제목 (Title(Eng.)) |
Packing edge-disjoint $K_5$-immersions in $4$-edge-connected graphs |
| 저자(Author(s)) |
Naonori Kakimura1, Ken-ichi Kawarabayashi2 University of Tokyo1, National Institute of Informatics and JST ERATO Kawarabayashi Project 2 |
| 초록본문(Abstract) | A graph $H$ is {\it immersed} in a graph $G$ if the vertices of $H$ are mapped to distinct vertices of $G$, and the edges of $H$ are mapped to paths joining the corresponding pairs of vertices of $G$, in such a way that the paths are pairwise edge-disjoint. In this talk, we show that the Erd\H{o}s-P\'{o}sa property holds for packing edge-disjoint $K_5$-immersions in $4$-edge-connected graphs. More precisely, for a positive integer $k$, there exists a constant $f(k)$ such that a $4$-edge-connected graph $G$ has either $k$ edge-disjoint $K_5$-immersions, or an edge subset $F$ of order at most $f(k)$ such that $G-F$ has no $K_5$-immersion. The $4$-edge-connectivity in this statement is best possible in the sense that $3$-edge-connected graphs do not have the Erd\H{o}s-P\'{o}sa property. |
| 분류기호 (MSC number(s)) |
05C83, 05C70 |
| 키워드(Keyword(s)) | immersion, packing, covering, 4-edge-connected graphs |
| 강연 형태 (Language of Session (Talk)) |
English |