Coverings by Few Monochromatic Pieces: A Transition Between Two Ramsey Problems

Gyárfás, András and Sárközy, Gábor and Selkow, Stanley (2015) Coverings by Few Monochromatic Pieces: A Transition Between Two Ramsey Problems. GRAPHS AND COMBINATORICS, 31 (1). pp. 131-140. ISSN 0911-0119

Preview

Text 1304.0871v1_1_u.pdf Download (147kB) | Preview

Abstract

The typical problem in (generalized) Ramsey theory is to find the order of the largest monochromatic member of a family {Mathematical expression} (for example matchings, paths, cycles, connected subgraphs) that must be present in any edge coloring of a complete graph Kn with t colors. Another area is to find the minimum number of monochromatic members of {Mathematical expression} that partition or cover the vertex set of every edge colored complete graph. Here we propose a problem that connects these areas: for a fixed positive integers s ≤ t, at least how many vertices can be covered by the vertices of no more than s monochromatic members of {Mathematical expression} in every edge coloring of Kn with t colors. Several problems and conjectures are presented, among them a possible extension of a well-known result of Cockayne and Lorimer on monochromatic matchings for which we prove an initial step: every t-coloring of Kn contains a (t - 1)-colored matching of size k provided that {Mathematical expression} © 2013 Springer Japan.

Actions (login required)

Edit Item