Anti-Ramsey Numbers for Forests and short cycles

Description of video

Date: 3/17/22
Speaker :Győri Ervin


    We call a subgraph of an edge-colored graph rainbow subgraph, if all of its edges have different colors. The anti-Ramsey number of a graph G in a complete graph of n vertices is the maximum number of colors in an edge-coloring of a complete graphs with no rainbow subgraph copy of G. In this paper, we determine the exact value of the anti-Ramsey number for star forests and the approximate value of the anti-Ramsey number for linear forests. Furthermore, we compute the exact value for two paths of 4 vertices, or double stars. We also study similar questions in complete r-partite graphs when we forbid special rainbow 3- or 4-cycles. Not surprisingly, they are related to the appropriate extremal numbers what were not easy to determine precisely.

    The lecture is based on three papers written jointly with some of Chunqiu Fang, Binglong Li, Mei Lu, Chuanqi Xiao,  Jimeng Xiao