Size and Degree Anti-Ramsey Numbers

Noga Alon

doi:10.1007/s00373-015-1583-9

Size and Degree Anti-Ramsey Numbers

Noga Alon

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	1833-1839
Number of pages	7
Journal	Graphs and Combinatorics
Volume	31
Issue number	6
DOIs	https://doi.org/10.1007/s00373-015-1583-9
State	Published - Jun 3 2015
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Anti-Ramsey
Proper edge coloring
Rainbow subgraph

Access to Document

10.1007/s00373-015-1583-9

Cite this

@article{bdc2cb532d21432f9cc3ac14b7b584c3,

title = "Size and Degree Anti-Ramsey Numbers",

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.",

keywords = "Anti-Ramsey, Proper edge coloring, Rainbow subgraph",

author = "Noga Alon",

note = "Publisher Copyright: {\textcopyright} 2015, Springer Japan.",

year = "2015",

month = jun,

day = "3",

doi = "10.1007/s00373-015-1583-9",

language = "English (US)",

volume = "31",

pages = "1833--1839",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "6",

}

TY - JOUR

T1 - Size and Degree Anti-Ramsey Numbers

AU - Alon, Noga

PY - 2015/6/3

Y1 - 2015/6/3

N2 - 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.

AB - 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.

KW - Anti-Ramsey

KW - Proper edge coloring

KW - Rainbow subgraph

UR - http://www.scopus.com/inward/record.url?scp=84946478729&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84946478729&partnerID=8YFLogxK

U2 - 10.1007/s00373-015-1583-9

DO - 10.1007/s00373-015-1583-9

M3 - Article

AN - SCOPUS:84946478729

SN - 0911-0119

VL - 31

SP - 1833

EP - 1839

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -

Size and Degree Anti-Ramsey Numbers

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this