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

DOI10.1007/S00373-013-1372-2zbMATH Open1306.05149arXiv1304.0871OpenAlexW2117187624MaRDI QIDQ489351FDOQ489351

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)

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.

Full work available at URL: https://arxiv.org/abs/1304.0871

Recommendations

• scientific article
• 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

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)

Cites Work

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

Cited In (10)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Perfect matchings in shadow colorings
• Matchings with few colors in colored complete graphs and hypergraphs
• Title not available (Why is that?)
• The (t−1) $(t-1)$‐chromatic Ramsey number for paths
• Lower bounds on the number of monochromatic matchings in \(K_{2s+t-1}\)
• Exponentially many monochromatic \(n\)-matchings in \(K_{3n-1}\)
• Monochromatic partitions in local edge colorings
• A generalization of Ramsey theory for stars and one matching
• 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)