8 papers
Multicolor Ramsey numbers of odd cycles are superexponential
Raphael Steiner
In a recent breakthrough, OpenAI proved that the -color Ramsey number of the triangle grows super-exponentially, more precisely, they proved that $R_k(C_3)\ge k^{k/3-o(k)}…
The ErdÅs-Hajnal conjecture for odd-girth
Raphael Steiner
A famous conjecture of ErdÅs and Hajnal from 1969 states that for every integer there exists a (smallest) function such that every…
A constant-factor step towards Vizing's conjecture
Raphael Steiner
Vizing's conjecture from 1963, considered by many the most important open problem in the field of graph domination, states that all graphs and satisfy $$γ(G\square H)\ge ΅
Openly disjoint cycles and directed tree-width of regular digraphs
Raphael Steiner
Given a digraph , let denote the largest integer such that there are openly disjoint cycles through a vertex, i.e., a collection of directed cycles $C_1,\ldots,C_…
A note on Ramsey numbers for minors
Maria Axenovich, Raphael Steiner
Let be the smallest integer such that any edge coloring of a complete graph on vertices in colors results in a monochromatic -minor, in other wor…
Coloring small locally sparse degenerate graphs and related problems
Domagoj BradaÄ, Jacob Fox, Raphael Steiner +2
The classic upper bound on the chromatic number of -degenerate graphs is , shown to be tight by complete graphs. A natural question is whether this bound remains tight if o…