The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.
While defining the anti-Ramsey number Erdős, Simonovits and Sós mentioned that the extremal colorings may not be unique. In the paper we discuss the uniqueness of the colorings, generalize the idea of their construction and show how to use it to construct the colorings of the edges of complete split graphs avoiding rainbow 2-connected subgraphs. These colorings give the lower bounds for adequate anti-Ramsey numbers.
A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f(n,H) is the maximum number of colors in an edge-coloring of Kₙ with no rainbow copy of H. The rainbow number rb(n,H) is the minimum number of colors such that any edge-coloring of Kₙ with rb(n,H) number of colors contains a rainbow copy of H. Certainly rb(n,H) = f(n,H) + 1. Anti-Ramsey numbers were introduced by Erdös et al. [5] and studied in...
Page 1