✦ LIBER ✦

A Characterisation of Pfaffian Near Bipartite Graphs

✍ Scribed by Ilse Fischer; Charles H.C. Little

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 622 KB
Volume: 82
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.2025

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is 1-extendible if every edge has a 1-factor containing it. A 1-extendible non-bipartite graph G is said to be near bipartite if there exist edges e 1 and e 2 such that G&[e 1 , e 2 ] is 1-extendible and bipartite. We characterise the Pfaffian near bipartite graphs in terms of forbidden subgraphs. The theorem extends an earlier characterisation of Pfaffian bipartite graphs.

2001 Academic Press

where u ij , w ij # VG* for all j. Associate with f i a plus sign if u i1 w i1 u i 2 w i 2 } } } u in w in

📜 SIMILAR VOLUMES

Convex hull of the edges of a graph and

Convex hull of the edges of a graph and near bipartite graphs

✍ J.-F Maurras 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 672 KB

A Characterization of Weakly Bipartite G

A Characterization of Weakly Bipartite Graphs

✍ Bertrand Guenin 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 889 KB

A signed graph is said to be weakly bipartite if the clutter of its odd circuits is ideal.

On the bipartite independence number of

On the bipartite independence number of a balanced bipartite graph

✍ Odile Favaron; Pedro Mago; Oscar Ordaz 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 603 KB

Venezuela Ap. 47567, Caracas Favaron, O., P. Mago and 0. Ordaz, On the bipartite independence number of a balanced bipartite graph, Discrete Mathematics 121 (1993) 55-63. The bipartite independence number GI aIp of a bipartite graph G is the maximum order of a balanced independent set of G. Let 6 b

On a product dimension of bipartite grap

On a product dimension of bipartite graphs

✍ S. Poljak; D. Rödl; A. Pultr 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 437 KB 👁 1 views

On 2-factors of a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 views

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2-factor with exactly k components? We will prove that if , then, for any bipartite graph H = (U 1 , U 2 ; F ) with |U 1 | ≤ n, |U 2 | ≤ n and ∆(H) ≤ 2, G contains a subgraph i

Partition of a bipartite graph into cycl

Partition of a bipartite graph into cycles

✍ Hong Wang 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 241 KB

Wang, H., Partition of bipartite graph into cycles, Discrete Mathematics 117 (1993) 287-291. El-Zahar (1984) conjectured that if G is a graph on n, + n, + + nk vertices with ni > 3 for 1s i < k and minimum degree 6(G)>rn,/21+rn2/21+ ... +rn,/21, then G contains k vertex-disjoint cycles of lengths n,