Rainbow Numbers for Graphs Containing Small Cycles.

For a given graph $$H$$ and $$n \ge 1,$$ let $$f(n, H)$$ denote the maximum number $$m$$ for which it is possible to colour the edges of the complete graph $$K_n$$ with $$m$$ colours in such a way that each subgraph $$H$$ in $$K_n$$ has at least two edges of the same colour. Equivalently, any edge-colouring of $$K_n$$ with at least $$rb(n,H)=f(n,H) + 1$$ colours contains a rainbow copy of $$H.$$ The numbers $$f(n,H)$$ and $$rb(K_n,H)$$ are called anti-ramsey numbers and rainbow numbers, respectively. In this paper we will classify the rainbow number for a given graph $$H$$ with respect to its cyclomatic number. Let $$H$$ be a graph of order $$p \ge 4$$ and cyclomatic number $$v(H) \ge 2.$$ Then $$rb(K_n, H)$$ cannot be bounded from above by a function which is linear in $$n.$$ If $$H$$ has cyclomatic number $$v(H) = 1,$$ then $$rb(K_n, H)$$ is linear in $$n.$$ Moreover, we will compute all rainbow numbers for the bull $$B,$$ which is the unique graph with $$5$$ vertices and degree sequence $$(1,1,2,3,3)$$ . [ABSTRACT FROM AUTHOR]