科研之友
微信
新浪微博
Facebook
分享链接
摘要
A copy of a graph H in an edge colored graph G is called rainbow if all edges of H have distinct colors. The size anti-Ramsey number of H, denoted by , is the smallest number of edges in a graph G such that any of its proper edge-colorings contains a rainbow copy of H. We show that . This settles a problem of Axenovich, Knauer, Stumpp and Ueckerdt. The proof is probabilistic and suggests the investigation of a related notion, which we call the degree anti-Ramsey number of a graph.
- 出版日期2015-11
