6 papers · 1 filter
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)}…
Locally bipartite subgraphs via multicolor Ramsey numbers
Raphael Steiner
A famous conjecture of Erdős and Hajnal (1969) states that for every integer there is a smallest function such that every graph of chromatic…
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…