Size and Degree Anti-Ramsey Numbers

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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 ARs(H), 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 ARs(Kk)=Θ(k6/log2k). 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.

Original languageEnglish (US)
Pages (from-to)1833-1839
Number of pages7
JournalGraphs and Combinatorics
Volume31
Issue number6
DOIs
StatePublished - Jun 3 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Anti-Ramsey
  • Proper edge coloring
  • Rainbow subgraph

Fingerprint Dive into the research topics of 'Size and Degree Anti-Ramsey Numbers'. Together they form a unique fingerprint.

Cite this