✦ LIBER ✦

Excluding a bipartite circle graph from line graphs

✍ Scribed by Sang-il Oum

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 215 KB
Volume: 60
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20353

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

Line graphs of bipartite graphs with Ham

Line graphs of bipartite graphs with Hamiltonian paths

✍ Francis K. Bell 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

It is shown that, if t is an integer !3 and not equal to 7 or 8, then there is a unique maximal graph having the path P t as a star complement for the eigenvalue À2: The maximal graph is the line graph of K m,m if t ¼ 2mÀ1, and of K m,m þ1 if t ¼ 2m. This result yields a characterization of L(G ) wh

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

A generalized construction of chromatic

A generalized construction of chromatic index critical graphs from bipartite graphs

✍ Michael Plantholt 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 378 KB

W e prove that any graph with maximum degree n which can be obtained by removing exactly 2n -1 edges from the join K? -K, ,, is n-critical This generalizes special constructions of critical graphs by S Fiorini and H P Yap, and suggests a possible extension of another general construction due to Yap

Quickly Excluding a Planar Graph

✍ N. Robertson; P. Seymour; R. Thomas 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 1014 KB

Bipartite graphs obtained from adjacency

Bipartite graphs obtained from adjacency matrices of orientations of graphs

✍ K.B. Reid 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 630 KB

If G denotes a graph of order n, then the adjacency matf;ix of an orientation G of G can be thought of as the adjacency matrix of a bipartite graph B(G) of order 2n, where the rows and columns correspond to the bipartition of B(G). For agraph H, let k(H) denote the number of connected components of

Independent edges in bipartite graphs ob

Independent edges in bipartite graphs obtained from orientations of graphs

✍ J. G. Gimbel; K. B. Reid 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 800 KB

## Abstract Given a digraph __D__ on vertices __v__~1~, __v__~2~, ⃛, __v__~__n__~, we can associate a bipartite graph __B(D)__ on vertices __s__~1~, __s__~2~, ⃛, __s__~__n__~, __t__~1~, __t__~2~, ⃛, __t__~__n__~, where __s__~__i__~__t__~__j__~ is an edge of __B(D)__ if (__v__~__i__~, __v__~__j__~)