Premium
Monochromatic connected matchings in 2‐edge‐colored multipartite graphs
Author(s) -
Balogh József,
Kostochka Alexandr,
Lavrov Mikhail,
Liu Xujun
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22797
Subject(s) - combinatorics , mathematics , multipartite , monochromatic color , 1 planar graph , indifference graph , connected component , strong perfect graph theorem , discrete mathematics , matching (statistics) , graph , chordal graph , edge coloring , cograph , line graph , graph power , statistics , quantum entanglement , quantum , biology , physics , botany , quantum mechanics
A matchingM $M$ in a graphG $G$ is connected if all the edges ofM $M$ are in the same component ofG $G$ . Following Łuczak, there have been many results using the existence of large connected matchings in cluster graphs with respect to regular partitions of large graphs to show the existence of long paths and other structures in these graphs. We prove exact Ramsey‐type bounds on the sizes of monochromatic connected matchings in 2‐edge‐colored multipartite graphs. In addition, we prove a stability theorem for such matchings.