𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nearly bipartite graphs

✍ Scribed by E. Győri; V. Nikiforov; R.H. Schelp

Book ID
108315877
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
148 KB
Volume
272
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Embeddings of cartesian products of near
Embeddings of cartesian products of nearly bipartite graphs
✍ Bojan Mohar; Tomaž Pisanski; Arthur T. White 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

## Abstract Surgical techniques are often effective in constructing genus embeddings of cartesian products of bipartite graphs. In this paper we present a general construction that is “close” to a genus embedding for cartesian products, where each factor is “close” to being bipartite. In specializi

Graphs without short odd cycles are near
Graphs without short odd cycles are nearly bipartite
✍ Ervin Györi; Alexandr V Kostochka; Tomasz Łuczak 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

It is proved that for every constant ~ > 0 and every graph G on n vertices which contains no odd cycles of length smaller than ~n, G can be made bipartite by removing (15/~}ln(10/~)) vertices. This resuIt is best possible except for a constant factor. Moreover, it is shown that one can destroy all o

High-Girth Graphs Avoiding a Minor are N
High-Girth Graphs Avoiding a Minor are Nearly Bipartite
✍ Anna Galluccio; Luis A. Goddyn; Pavol Hell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 166 KB

Let H be a fixed graph. We show that any H-minor free graph G of high enough girth has circular chromatic number arbitrarily close to two. Equivalently, each such graph G admits a homomorphism to a large odd circuit. In particular, graphs of high girth and of bounded genus, or of bounded tree width,