✦ LIBER ✦

On the Ramsey Problem for Multicolor Bipartite Graphs

✍ Scribed by W.A Carnielli; E.L Monte Carmelo

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 85 KB
Volume: 22
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.1998.0620

No coin nor oath required. For personal study only.

✦ Synopsis

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 matrix a = a with entries in 0, 1, . . . , r y 1 r always contains a submatrix m = n or n = m whose entries are i, 0 F i F r y 1. Ž . m Ž . my 1

We shall prove that R m, n F 2 n y 1 q 2 y 1, which generalizes the 2 Ž . Ž . previous results R 2, n F 4 n y 3 and R 3, n F 8 n y 5 due to Beineke and 2 2

Schwenk. Moreover, we find a class of lower bounds based on properties of Ž . y2 orthogonal Latin squares which establishes that lim R 2, 2 r s 1. ᮊ 1999 r ª ϱ r

📜 SIMILAR VOLUMES

A new upper bound for the bipartite Rams

A new upper bound for the bipartite Ramsey problem

✍ David Conlon 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB 👁 1 views

## Abstract We consider the following question: how large does __n__ have to be to guarantee that in any two‐coloring of the edges of the complete graph __K__~__n,n__~ there is a monochromatic __K__~__k,k__~? In the late 1970s, Irving showed that it was sufficient, for __k__ large, that __n__ ≥ 2^_

An extremal bandwidth problem for bipart

An extremal bandwidth problem for bipartite graphs

✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 2 views

Short Solution of Kotzig's Problem for B

Short Solution of Kotzig's Problem for Bipartite Graphs

✍ A.S. Asratian 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 263 KB

In 1975, A. Kotzig posed the following problem: Let G be a t-regular graph which has a proper edge t-coloring, t 4. Is it possible to obtain, from one proper edge t-coloring of G, any other proper edge t-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the inte

On Generalized Ramsey Theory: The Bipart

On Generalized Ramsey Theory: The Bipartite Case

✍ Maria Axenovich; Zoltán Füredi; Dhruv Mubayi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 208 KB

On irredundant Ramsey numbers for graphs

✍ Johannes H. Hattingh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB

## Abstract The irredundant Ramsey number __s(m, n)__ is the smallest p such that in every two‐coloring of the edges of __K~p~__ using colors red (__R__) and blue (__B__), either the blue graph contains an __m__‐element irredundant set or the red graph contains an __n__‐element irredundant set. We

NP completeness of the edge precoloring

NP completeness of the edge precoloring extension problem on bipartite graphs

✍ Jiří Fiala 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co