Premium
Large monochromatic components in multicolored bipartite graphs
Author(s) -
DeBiasio Louis,
Krueger Robert A.,
Sárközy Gábor N.
Publication year - 2020
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.22510
Subject(s) - bipartite graph , combinatorics , mathematics , corollary , conjecture , monochromatic color , complete bipartite graph , discrete mathematics , degree (music) , graph , physics , acoustics , optics
Abstract It is well known that in every r ‐coloring of the edges of the complete bipartite graph K m , nthere is a monochromatic connected component with at least( m + n ) / r vertices. In this paper we study an extension of this problem by replacing complete bipartite graphs by bipartite graphs of large minimum degree. We conjecture that in every r ‐coloring of the edges of an ( X , Y ) ‐bipartite graph with| X | = m , | Y | = n , δ ( X , Y ) > ( 1 − 1 / ( r + 1 )) n , and δ ( Y , X ) > ( 1 − 1 / ( r + 1 ) ) m , there exists a monochromatic component on at least( m + n ) / r vertices (as in the complete bipartite graph). If true, the minimum degree condition is sharp (in that both inequalities cannot be made weak when m and n are divisible by r + 1 ). We prove the conjecture for r = 2 and we prove a weaker bound for all r ≥ 3. As a corollary, we obtain a result about the existence of monochromatic components with at least n /( r − 1) vertices in r ‐colored graphs with large minimum degree.