Coverings by few monochromatic pieces: a transition between two Ramsey problems

DOI10.1007/S00373-013-1372-2MaRDI QIDQ489351zbMATH OpenOpenAlexFDO

Authors András Gyárfás, Gábor N. Sárközy, Stanley Selkow

Publication date 20 January 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.0871, http://real.mtak.hu/33630/1/1304.0871v1_1_u.pdf

zbMATH Keywords

matchingsRamsey problemsmonochromatic coverings

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Ramsey theory (05D10)

Abstract: The typical problem in (generalized) Ramsey theory is to find the order of the largest monochromatic member of a family F (for example matchings, paths, cycles, connected subgraphs) that must be present in any edge coloring of a complete graph K_n with t colors. Another area is to find the minimum number of monochromatic members of F that partition or cover the vertex set of every edge colored complete graph. Here we propose a problem that connects these areas: for fixed positive integers s,t, at least how many vertices can be covered by the vertices of no more than s monochromatic members of F in every edge coloring of K_n 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: in case of s=t-1 we determine how many vertices can be covered by s monochromatic matchings in every t-coloring of K_n.

Recommendations

• scientific article; zbMATH DE number 4154488
• A generalization of Ramsey theory for stars and one matching
• Lower bounds on the number of monochromatic matchings in \(K_{2s+t-1}\)
• Matchings with few colors in colored complete graphs and hypergraphs
• Vertex coverings by monochromatic cycles and trees

Cites work

• scientific article; zbMATH DE number 1185305 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• A generalization of Ramsey theory for graphs
• A generalization of Ramsey theory for linear forests
• Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
• Generalized Ramsey numbers for paths in 2-chromatic graphs
• Large monochromatic components in edge colorings of graphs: A survey
• On maximal paths and circuits of graphs
• One-sided coverings of colored complete bipartite graphs
• Partitioning 3-colored complete graphs into three monochromatic cycles
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Ramsey Theorems for Multiple Copies of Graphs
• Ramsey numbers for multiple copies of complete graphs
• The Ramsey number for a triple of long even cycles
• The Ramsey number for stripes
• The Ramsey number of diamond-matchings and loose cycles in hypergraphs
• Three-color Ramsey numbers for paths
• Vertex coverings by monochromatic cycles and trees
• Vertex coverings by monochromatic paths and cycles

Cited in

(12)

• A generalization of Ramsey theory for stars and one matching
• Monochromatic partitions in local edge colorings
• Matchings with few colors in colored complete graphs and hypergraphs
• The (t−1) $(t-1)$‐chromatic Ramsey number for paths
• Exponentially many monochromatic \(n\)-matchings in \(K_{3n-1}\)
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Perfect matchings in shadow colorings
• Lower bounds on the number of monochromatic matchings in \(K_{2s+t-1}\)
• Monochromatic spanning trees and matchings in ordered complete graphs
• Ramsey-Turán type results for matchings in edge colored graphs
• scientific article; zbMATH DE number 4154488 (Why is no real title available?)
• Large monochromatic components in edge colorings of graphs: A survey

This page was built for publication: Coverings by few monochromatic pieces: a transition between two Ramsey problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489351)