Monochromatic coverings and tree Ramsey numbers

DOI10.1016/0012-365X(94)90179-1MaRDI QIDQ1322294zbMATH OpenOpenAlexFDO

Authors Zsolt Tuza

Publication date 5 May 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)90179-1

zbMATH Keywords

complete graphcoveringsRamsey numbers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The main result of this paper is the following Ramsey type theorem. Let \(k=3\) or 4 and let \(n\) be a natural number not divisible by \(k-1\). Consider any edge \(k\)-coloring of the complete graph \(K_ p\) where \(p=(k-1) (n-1)+2\). Then \(K_ p\) admits \(k-1\) monochromatic connected subgraphs \(G_ 1, \dots, G_{k-1}\) so that \[ | V (G_ 1) | \geq n+1 \text{ and } V(G_ 1) \cup V(G_ 2) \cup \cdots \cup V (G_{k- 1})=V (K_ p). \] Some partial results are also obtained for \(k>4\).

Recommendations

• On generalized Ramsey numbers for trees
• scientific article; zbMATH DE number 2197938
• An upper bound on the Ramsey number of trees
• Partitioning complete multipartite graphs by monochromatic trees
• More on monochromatic-rainbow Ramsey type theorems

Cites work

• An upper bound on the Ramsey number of trees
• scientific article; zbMATH DE number 3884213 (Why is no real title available?)
• scientific article; zbMATH DE number 4065037 (Why is no real title available?)
• scientific article; zbMATH DE number 4070935 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• scientific article; zbMATH DE number 3334898 (Why is no real title available?)
• Maximum degree and fractional matchings in uniform hypergraphs
• Multipartite Turán problem for connected graphs and hypergraphs
• On generalized Ramsey numbers for trees

Cited in

(9)

• On generalized Ramsey numbers for trees
• Ramsey numbers and monotone colorings
• Generalizations and strengthenings of Ryser's conjecture
• Ramsey numbers of path-matchings, covering designs, and 1-cores
• Monochromatic tree covers and Ramsey numbers for set-coloured graphs
• scientific article; zbMATH DE number 1498635 (Why is no real title available?)
• Ramsey theory for monochromatically well-connected subsets
• scientific article; zbMATH DE number 2197938 (Why is no real title available?)
• Covering random graphs with monochromatic trees

This page was built for publication: Monochromatic coverings and tree Ramsey numbers

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