NDA
Bejelentkezés
Kapcsolat
Ramsey number of paths and connected matchings in Ore-type host graphs |
Tartalom: | http://real.mtak.hu/43724/ |
---|---|
Archívum: | MTA Könyvtár |
Gyűjtemény: |
Status = Published
Type = Article |
Cím: |
Ramsey number of paths and connected matchings in Ore-type host graphs
|
Létrehozó: |
Barát, János
Gyárfás, András
Lehel, JĂłzsef
Sárközy, Gábor
|
Kiadó: |
North-Holland Publishing Company
|
Dátum: |
2016
|
Téma: |
QA166-QA166.245 Graphs theory / gráfelmélet
QA71 Number theory / számelmélet
|
Tartalmi leírás: |
It is well-known (as a special case of the path-path Ramsey number) that in every 2-coloring of the edges of K3(n-1), the complete graph on 3n - 1 vertices, there is a monochromatic P-2n, a path on 2n vertices. Schelp conjectured that this statement remains true if K3n-1 is replaced by any host graph on 3n - 1 vertices with minimum degree at least 3(3n-1)/4. Here we propose the following stronger conjecture, allowing host graphs with the corresponding Ore-type condition: If G is a graph on 3n - 1 vertices such that for any two non-adjacent vertices u and v, d(G)(u) + d(G)(v) >= 3/2 (3n - 1), then in any 2-coloring of the edges of G there is a monochromatic path on 2n vertices. Our main result proves the conjecture in a weaker form, replacing P-2n by a connected matching of size n. Here a monochromatic, say red, matching in a 2-coloring 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.
|
Nyelv: |
angol
|
Típus: |
Article
PeerReviewed
info:eu-repo/semantics/article
|
Formátum: |
text
|
Azonosító: |
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 Ore-type host graphs. DISCRETE MATHEMATICS, 339 (6). pp. 1690-1698. ISSN 0012-365X
|
Kapcsolat: |
MTMT:3066835; doi:10.1016/j.disc.2016.01.014
|