Excluding a bipartite circle graph from line graphs |
| |
| Authors: | Sang‐il Oum |
| |
| Affiliation: | 1. Department of Mathematical Sciences, Kaist, Daejeon 305‐701, Republic of Korea;2. The research was partially done while the author was at Georgia Institute of Technology. |
| |
| Abstract: | We prove that, for a fixed bipartite circle graph H, all line graphs with sufficiently large rank‐width (or clique‐width) must have a pivot‐minor isomorphic to H. To prove this, we introduce graphic delta‐matroids. Graphic delta‐matroids are minors of delta‐matroids of line graphs and they generalize graphic and cographic matroids. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 183–203, 2009 |
| |
| Keywords: | rank‐width circle graph line graph pivot‐minor graphic delta‐matroid tree‐width |
|
|
