Long monochromatic paths and cycles in 2-colored bipartite graphs

DOI10.1016/J.DISC.2020.111907zbMATH Open1441.05072arXiv1806.05119OpenAlexW3013984945MaRDI QIDQ2185910FDOQ2185910

Robert A. Krueger, Louis DeBiasio

Publication date: 8 June 2020

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

Abstract: Gy'arf'as and Lehel and independently Faudree and Schelp proved that in any 2-coloring of the edges of $K_{n,n}$ there exists a monochromatic path on at least $2lceiln/2ceil$ vertices, and this is tight. We prove a stability version of this result which holds even if the host graph is not complete; that is, if $G$ is a balanced bipartite graph on $2n$ vertices with minimum degree at least $(3/4+o(1))n$, then in every 2-coloring of the edges of $G$, either there exists a monochromatic cycle on at least $(1+o(1))n$ vertices, or the coloring of $G$ is close to an extremal coloring -- in which case $G$ has a monochromatic path on at least $2lceiln/2ceil$ vertices and a monochromatic cycle on at least $2lfloorn/2floor$ vertices. Furthermore, we determine an asymptotically tight bound on the length of a longest monochromatic cycle in a 2-colored balanced bipartite graph on $2n$ vertices with minimum degree $deltan$ for all $0leqdeltaleq1$.

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

zbMATH Keywords

stabilityconnected matching

Mathematics Subject Classification ID

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

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?)
• Embedding large subgraphs into dense graphs
• \(R(C_n,C_n,C_n)\leqq (4+o(1))n\)
• Monochromatic cycles in 2-coloured graphs
• Star versus two stripes Ramsey numbers and a conjecture of Schelp
• A Ramsey-type problem in directed and bipartite graphs
• Stability of the path-path Ramsey number
• Generalizing the Ramsey problem through diameter
• Highly connected monochromatic subgraphs of multicolored graphs
• Path-path Ramsey type numbers for the complete bipartite graph
• The Monochromatic Circumference of 2‐Edge‐Colored Graphs

Cited In (3)

• Monochromatic components in edge-coloured graphs with large minimum degree
• Large monochromatic components in almost complete graphs and bipartite graphs
• Monochromatic connected matchings in 2‐edge‐colored multipartite graphs

This page was built for publication: Long monochromatic paths and cycles in 2-colored bipartite graphs

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