Barát, János and Gyárfás, András and Lehel, József and Sárközy, Gábor (2016) Ramsey number of paths and connected matchings in Oretype host graphs. DISCRETE MATHEMATICS, 339 (6). pp. 16901698. ISSN 0012365X

Text
8d47ef71b8766ef5e67a0d40bfed0d6f8172.pdf Download (188kB)  Preview 
Abstract
It is wellknown (as a special case of the pathpath Ramsey number) that in every 2coloring of the edges of K3(n1), the complete graph on 3n  1 vertices, there is a monochromatic P2n, a path on 2n vertices. Schelp conjectured that this statement remains true if K3n1 is replaced by any host graph on 3n  1 vertices with minimum degree at least 3(3n1)/4. Here we propose the following stronger conjecture, allowing host graphs with the corresponding Oretype condition: If G is a graph on 3n  1 vertices such that for any two nonadjacent vertices u and v, d(G)(u) + d(G)(v) >= 3/2 (3n  1), then in any 2coloring of the edges of G there is a monochromatic path on 2n vertices. Our main result proves the conjecture in a weaker form, replacing P2n by a connected matching of size n. Here a monochromatic, say red, matching in a 2coloring of the edges of a graph is connected if its edges are all in the same connected component of the graph defined by the red edges. Applying the standard technique of converting connected matchings to paths with the Regularity Lemma, we use this result to get an asymptotic version of our conjecture for paths. (C) 2016 Elsevier B.V. All rights reserved.
Item Type:  Article 

Uncontrolled Keywords:  THEOREM; cycles; Oretype graphs; Connected matchings; PATHS; Ramsey numbers 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet Q Science / természettudomány > QA Mathematics / matematika > QA71 Number theory / számelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  21 Dec 2016 12:05 
Last Modified:  21 Dec 2016 12:06 
URI:  http://real.mtak.hu/id/eprint/43724 
Actions (login required)
Edit Item 