Linear upper bounds for local Ramsey numbers

Miroslaw Truszczynski, Zsolt Tuza

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

A coloring of the edges of a graph is called a local k-coloring if every vertex is incident to edges of at most k distinct colors. For a given graph G, the local Ramsey number, rlock(G), is the smallest integer n such that any local k-coloring of Kn, (the complete graph on n vertices), contains a monochromatic copy of G. The following conjecture of Gyárfás et al. is proved here: for each positive integer k there exists a constant c = c(k) such that rlock(G) ≤ crk(G), for every connected grraph G (where rk(G) is the usual Ramsey number for k colors). Possible generalizations for hypergraphs are considered.

Original languageEnglish
Pages (from-to)67-73
Number of pages7
JournalGraphs and Combinatorics
Volume3
Issue number1
DOIs
StatePublished - Dec 1987

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Linear upper bounds for local Ramsey numbers'. Together they form a unique fingerprint.

Cite this