Anti-Ramsey theory on complete bipartite graphs. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Cho, Stephan; Cummings, Jay; Defant, Colin; Sonneborn, Claire
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 948
• Page End: 951
• Publication Date: 2020-09-01
• Subjects: Graph coloring -- bipartite -- rainbow -- edge-coloring -- latin square -- projective plane; Primary 05C15 -- Secondary 05B15
• DOI: 10.1016/j.akcej.2019.08.010
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: We consider quadruples of positive integers ( a, b, m, n ) with a ≤ b and m ≤ n such that every proper edge-coloring of the complete bipartite graph K m, n contains a rainbow K a, b subgraph. We show that every such quadruple with m ≥ a and n > ( a 2 − a + 1 ) ( b − 1 ) satisfies this property and find an infinite sequence where this bound is sharp. We also define and compute some new anti-Ramsey numbers.