On the Ramsey Numbers for Bipartite Multigraphs

Original · EN

A coloring of a complete bipartite graph is shuffle-preserved if it is the case that assigning a color c to edges (u, v) and (u', v') enforces the same color assignment for edges (u, v') and (u',v). (In words, the induced subgraph with respect to color c is complete.) In this paper, we investigate a variant of the Ramsey problem for the class of complete bipartite multigraphs. (By a multigraph we mean a graph in which multiple edges, but no loops, are allowed.) Unlike the conventional m-coloring scheme in Ramsey theory which imposes a constraint (i.e., m) on the total number of colors allowed in a graph, we introduce a relaxed version called m-local coloring which only requires that, for every vertex v, the number of colors associated with v's incident edges is bounded by m. Note that the number of colors found in a graph under m-local coloring may exceed m. We prove that given any n × n complete bipartite multigraph G, every shuffle-preserved m-local coloring displays a monochromatic copy of Kₚ,ₚ provided that 2(p-1)(m-1) < n. Moreover, the above bound is tight when (i) m=2, or (ii) n=2ᵏ and m=3· 2ᵏ⁻² for every integer k≥ 2. As for the lower bound of p, we show that the existence of a monochromatic Kₚ,ₚ is not guaranteed if p> n/m. Finally, we give a generalization for k-partite graphs and a method applicable to general graphs. Many conclusions found in m-local coloring can be inferred to similar results of m-coloring.