Premium
Excluding a bipartite circle graph from line graphs
Author(s) -
Oum Sangil
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20353
Subject(s) - combinatorics , matroid , mathematics , bipartite graph , line graph , discrete mathematics , block graph , graph , graphic matroid , pathwidth
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