Picollelli, Michael E.

An anti-Ramsey condition on trees

Electron. J. Comb. 15(1), Research Paper R24, 23 p. (2008)


Summary: 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.

Mathematics Subject Classification

05C05, 05C15, 05C55