An Anti-Ramsey Condition on Trees

Michael E. Picollelli


Let $H$ be a finite tree. We consider trees $T$ such that if the edges of $T$ are colored so that no color occurs more than $b$ times, then $T$ has a subgraph isomorphic to $H$ in which no color is repeated. We will show that if $H$ falls into a few classes of trees, including those of diameter at most $4$, then the minimum value of $e(T)$ is provided by a known construction, supporting a conjecture of Bohman, Frieze, Pikhurko and Smyth.

Full Text: PDF