Avoiding k-Rainbow Graphs in Edge Colorings of Kn and other Families of Graphs

Abstract

A simple graph, G, avoids a k-rainbow edge coloring if any color appears on at least k + 1 edges of G. For any positive integer k, the k-Anti-Ramsey Number, ARk(G,H), is the maximum number of colors in an edge coloring of the graph H such that no k-rainbow edge colored copy of G is a subgraph of H. This work will discuss ARk(G,H) where H is various types of graphs. In particular, this work will focus on ARk(G,Kn) and define G as ARk-bounded if ARk(G,Kn) is bounded by some positive integer c for all n sufficiently large. Additionally, we will say G is ARk-unbounded is no such positive integer exists. In this work we will determine which simple graphs are ARk-bounded for any k. We will provide a lower bound for ARk(G,Kn) if G is ARk-unbounded and an upper bound for ARk(G,Kn) if G is ARk-bounded. We will also determine ARk(G,H) for various graphs G, H where H is not a complete graph.