Three-Color Bipartite Ramsey Number for Graphs with Small Bandwidth

DOI10.1137/18M1179420zbMATH Open1403.05096arXiv1804.02451OpenAlexW2963737636MaRDI QIDQ4611005FDOQ4611005

G. O. Mota

Publication date: 23 January 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We estimate the $3$-colour bipartite Ramsey number for balanced bipartite graphs $H$ with small bandwidth and bounded maximum degree. More precisely, we show that the minimum value of $N$ such that in any $3$-edge colouring of $K_{N,N}$ there is a monochromatic copy of $H$ is at most $$. In particular, we determine asymptotically the $3$-colour bipartite Ramsey number for balanced grid graphs.

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

zbMATH Keywords

bandwidthregularity lemmabipartite Ramsey number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Generalized Ramsey theory (05C55)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ramsey numbers for trees of small maximum degree
• The 3-colored Ramsey number of even cycles
• \(R(C_n,C_n,C_n)\leqq (4+o(1))n\)
• Path Ramsey numbers in multicolorings
• Three-color Ramsey numbers for paths
• Tripartite Ramsey numbers for paths
• The Ramsey number for a triple of long even cycles
• All Ramsey numbers for cycles in graphs
• Blow-up lemma
• A Ramsey-type problem in directed and bipartite graphs
• On finite Ramsey numbers
• Ramsey functions involving \(K_{m,n}\) with \(n\) large
• A new upper bound for the bipartite Ramsey problem
• On a Ramsey-type problem of J. A. Bondy and P. Erdős. II
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Small Ramsey numbers
• The Ramsey number for hypergraph cycles. I.
• An algorithmic version of the blow-up lemma
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• The bipartite Ramsey numbers
• Ramsey numbers for bipartite graphs with small bandwidth
• Recent developments in graph Ramsey theory
• Hypergraph Packing and Graph Embedding
• 3‐Color bipartite Ramsey number of cycles and paths
• Embedding into Bipartite Graphs

Cited In (2)

• Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth
• Bipartite Ramsey numbers for graphs of small bandwidth

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Three-color Ramsey numbers for paths 👍 👎
• On some three-color Ramsey numbers for paths 👍 👎
• Ramsey numbers for bipartite graphs with small bandwidth 👍 👎
• On some three color Ramsey numbers for paths and cycles 👍 👎
• 3‐Color bipartite Ramsey number of cycles and paths 👍 👎
• Bipartite Ramsey numbers for graphs of small bandwidth 👍 👎
• Three color Ramsey numbers for graphs with at most 4 vertices 👍 👎
• Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth 👍 👎

This page was built for publication: Three-Color Bipartite Ramsey Number for Graphs with Small Bandwidth

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