Opuscula Math. 37, no. 4 (2017), 567-575
http://dx.doi.org/10.7494/OpMath.2017.37.4.567

Opuscula Mathematica

# Anti-Ramsey numbers for disjoint copies of graphs

Izolda Gorgol
Agnieszka Görlich

Abstract. A subgraph of an edge-colored graph is called rainbow if all of its edges have different colors. For a graph $$G$$ and a positive integer $$n$$, the anti-Ramsey number $$ar(n,G)$$ is the maximum number of colors in an edge-coloring of $$K_n$$ with no rainbow copy of $$H$$. Anti-Ramsey numbers were introduced by Erdȍs, Simonovits and Sós and studied in numerous papers. Let $$G$$ be a graph with anti-Ramsey number $$ar(n,G)$$. In this paper we show the lower bound for $$ar(n,pG)$$, where $$pG$$ denotes $$p$$ vertex-disjoint copies of $$G$$. Moreover, we prove that in some special cases this bound is sharp.

Keywords: anti-Ramsey number, rainbow number, disjoint copies.

Mathematics Subject Classification: 05C55, 05C15.

Full text (pdf)