𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Balanced cycles and holes in bipartite graphs

✍ Scribed by Michele Conforti; Gérard Cornuéjols; Kristina Vušković

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
414 KB
Volume
199
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Bruce Reed asks the following question: Can we determine whether a bipartite graph contains a chordless cycle whose length is a multiple of 4? We show that the two following more general questions are equivalent and we provide an answer. Given a bipartite graph G where each edge is assigned a weight + 1 or -I, l determine whether G contains a cycle whose weight is a multiple of 4, l determine whether G contains a chordless cycle whose weight is a multiple of 4. Given a bipartite graph, we can also decide whether it is possible to assign weights + I or -1 to its edges so that the above two properties hold.

📜 SIMILAR VOLUMES

Balanced coloring of bipartite graphs
Balanced coloring of bipartite graphs
✍ Uriel Feige; Shimon Kogan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract Given a bipartite graph __G__(__U__∪__V, E__) with __n__ vertices on each side, an independent set __I__∈__G__ such that |__U__∩__I__|=|__V__∩__I__| is called a balanced bipartite independent set. A balanced coloring of __G__ is a coloring of the vertices of __G__ such that each color c

Longest paths and cycles in bipartite or
Longest paths and cycles in bipartite oriented graphs
✍ Zhang Ke Min 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB 👁 1 views

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense. An oriented graph is a digraph without

Dominating cycles in bipartite biclaw-fr
Dominating cycles in bipartite biclaw-free graphs
✍ Daniel Barraez; Evelyne Flandrin; Hao Li; Oscar Ordaz 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 354 KB

Flandrin et ai. (to appear) define a simple bipartite graph to be biclaw-free if it contains no induced subgraph isomorphic to H, where H could be obtained from two copies of K1.3 by adding an edge joining the two vertices of degree 3. They have shown that if G is a bipartite, balanced, biclaw-free

Biclosure and bistability in a balanced
Biclosure and bistability in a balanced bipartite graph
✍ Denise Amar; Odile Favaron; Pedro Mago; Oscar Ordaz 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 719 KB

## Abstract The __k__‐biclosure of a balanced bipartite graph wiht color classes __A__ and __B__ is the graph obtained from __G__ by recursively joining pairs of nonadjacent vertices respectively taken in __A__ and __B__ whose degree sum is at least __k__, until no such pair remains. A property __P