Monochromatic balanced components, matchings, and paths in multicolored complete bipartite graphs

DOI10.4310/JOC.2020.V11.N1.A2zbMATH Open1427.05087arXiv1804.04195WikidataQ127198828 ScholiaQ127198828MaRDI QIDQ2335906FDOQ2335906

Authors: Louis DeBiasio, Robert A. Krueger, Miklós Ruszinkó, Gábor N. Sárközy, András Gyárfás 

Publication date: 18 November 2019

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: It is well-known that in every $r$-coloring of the edges of the complete bipartite graph $K_{n,n}$ there is a monochromatic connected component with at least $2noverr$ vertices. It would be interesting to know whether we can additionally require that this large component be balanced; that is, is it true that in every $r$-coloring of $K_{n,n}$ there is a monochromatic component that meets both sides in at least $n/r$ vertices? Over forty years ago, Gy'arf'as and Lehel and independently Faudree and Schelp proved that any $2$-colored $K_{n,n}$ contains a monochromatic $P_n$. Very recently, Buci'c, Letzter and Sudakov proved that every $3$-colored $K_{n,n}$ contains a monochromatic connected matching (a matching whose edges are in the same connected component) of size $lceiln/3ceil$. So the answer is strongly "yes" for $1leqrleq3$. We provide a short proof of (a non-symmetric version of) the original question for $1leqrleq3$; that is, every $r$-coloring of $K_{m,n}$ has a monochromatic component that meets each side in a $1/r$ proportion of its part size. Then, somewhat surprisingly, we show that the answer to the question is "no" for all $rge4$. For instance, there are $4$-colorings of $K_{n,n}$ where the largest balanced monochromatic component has $n/5$ vertices in both partite classes (instead of $n/4$). Our constructions are based on lower bounds for the $r$-color bipartite Ramsey number of $P_4$, denoted $f(r)$, which is the smallest integer $ell$ such that in every $r$-coloring of the edges of $K_{ell,ell}$ there is a monochromatic path on four vertices. Furthermore, combined with earlier results, we determine $f(r)$ for every value of $r$.

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

Recommendations

• Large monochromatic components in multicolored bipartite graphs
• One-sided coverings of colored complete bipartite graphs
• Partitioning complete bipartite graphs by monochromatic cycles
• Multicolor bipartite Ramsey number of \(C_{4}\) and large \(K_{n, n}\)
• Long monochromatic paths and cycles in 2-colored bipartite graphs

zbMATH Keywords

bipartite graphRamsey

Mathematics Subject Classification ID

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

Cited In (7)

• Multicolour bipartite Ramsey number of paths
• Long monochromatic paths and cycles in 2-colored bipartite graphs
• Large monochromatic components in multicolored bipartite graphs
• Bipartite Ramsey numbers of cycles
• The (t−1) $(t-1)$‐chromatic Ramsey number for paths
• Long monochromatic paths and cycles in 2-edge-colored multipartite graphs
• Monochromatic connected matchings in 2‐edge‐colored multipartite graphs

This page was built for publication: Monochromatic balanced components, matchings, and paths in multicolored complete bipartite graphs

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