Anti-Ramsey theory on complete bipartite graphs

Abstract

We consider quadruples of positive integers with and such that every proper edge-coloring of the complete bipartite graph contains a rainbow subgraph. We show that every such quadruple with and satisfies this property and find an infinite sequence where this bound is sharp. We also define and compute some new anti-Ramsey numbers.

Keywords

• graph coloring
• bipartite
• rainbow
• edge-coloring
• latin square
• projective plane