𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Ramsey graphs without bipartite subgraphs

✍ Scribed by Jaroslav Nešetřil; Vojtěch Rödl

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
388 KB
Volume
101
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

NeSetfil, J. and V. Riidl, On Ramsey graphs without bipartite subgraphs, Discrete Mathematics 101 (1992) 223-229.

We prove that for every graph H without triangles and K,,,,,m, n G 2, there exists a Ramsey graph with the same properties.

This answers a problem due to Erd& and Faudree. Moreover we characterize all (edge-) Ramsey classes Forb(K,,,).

📜 SIMILAR VOLUMES

On the Ramsey Problem for Multicolor Bip
On the Ramsey Problem for Multicolor Bipartite Graphs
✍ W.A Carnielli; E.L Monte Carmelo 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 85 KB

Given i, j positive integers, let K denote a bipartite complete graph and let i, j ## Ž . R m, n be the smallest integer a such that for any r-coloring of the edges of K r a, a one can always find a monochromatic subgraph isomorphic to K . In other m, n Ž . Ä 4 words, if a G R m, n then every mat

Finite Induced Graph Ramsey Theory: On P
Finite Induced Graph Ramsey Theory: On Partitions of Subgraphs
✍ D.S. Gunderson; V. Rodl; N.W. Sauer 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 425 KB

For given finite (unordered) graphs \(G\) and \(H\), we examine the existence of a Ramsey graph \(F\) for which the strong Ramsey arrow \(F \rightarrow(G)_{r}^{\prime \prime}\) holds. We concentrate on the situation when \(H\) is not a complete graph. The set of graphs \(G\) for which there exists a

On maximum bipartite subgraphs
On maximum bipartite subgraphs
✍ Günther Malle 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 314 KB

## Abstract In this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipa

A note on bipartite subgraphs of triangl
A note on bipartite subgraphs of triangle-free regular graphs
✍ S. C. Locke 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

## Abstract Lower bounds on the size of a maximum bipartite subgraph of a triangle‐free __r__‐regular graph are presented.