Raphael Steiner

activity

20242026

collaborators

11 papers

math.CO2026

Multicolor Ramsey numbers of odd cycles are superexponential

Raphael Steiner

In a recent breakthrough, OpenAI proved that the $k$ -color Ramsey number of the triangle $C_{3}$ grows super-exponentially, more precisely, they proved that $R_k(C_3)\ge k^{k/3-o(k)}…

math.CO2026

Locally bipartite subgraphs via multicolor Ramsey numbers

Raphael Steiner

A famous conjecture of Erdős and Hajnal (1969) states that for every integer $g \geq 4$ there is a smallest function $f_{g} : N \to N$ such that every graph of chromatic…

math.CO2026

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 $G$ and $H$ satisfy $$γ(G\square H)\ge γ(…

math.CO2026

Openly disjoint cycles and directed tree-width of regular digraphs

Raphael Steiner

Given a digraph $D$ , let $c (D)$ denote the largest integer $k$ such that there are $k$ openly disjoint cycles through a vertex, i.e., a collection of directed cycles $C_1,\ldots,C_…

math.CO2026

A note on Ramsey numbers for minors

Maria Axenovich, Raphael Steiner

Let $R_{h} (k; ℓ)$ be the smallest integer $n$ such that any edge coloring of a complete graph on $n$ vertices in $ℓ$ colors results in a monochromatic $K_{k}$ -minor, in other wor…

math.CO2026

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 $d$ -degenerate graphs is $d + 1$ , shown to be tight by complete graphs. A natural question is whether this bound remains tight if o…

math.CO2025

Defective coloring of blowups

Sergey Norin, Raphael Steiner

Given a graph $G$ and an integer $d \geq 0$ , its $d$ -defective chromatic number $χ^{d} (G)$ is the smallest size of a partition of the vertices into parts inducing subgraphs with maximu…

cs.CG2025

Geometric realizations of dichotomous ordinal graphs

Patrizio Angelini, Sabine Cornelsen, Carolina Haase +5

A dichotomous ordinal graph consists of an undirected graph with a partition of the edges into short and long edges. A geometric realization of a dichotomous ordinal graph $G$ in a…

math.CO2024

Fractional chromatic number vs. Hall ratio

Raphael Steiner

Given a graph $G$ , its Hall ratio $ρ (G) = max_{H \subseteq G} \frac{∣ V ( H ) ∣}{α ( H )}$ forms a natural lower bound on its fractional chromatic number $χ_{f} (G)$ . A recent line of research s…

math.CO2024

Chromatic number and regular subgraphs

Barnabás Janzer, Raphael Steiner, Benny Sudakov

In 1992, Erdős and Hajnal posed the following natural problem: Does there exist, for every $r \in N$ , an integer $F (r)$ such that every graph with chromatic number at least…

math.CO2024

On the difference between the chromatic and cochromatic number

Raphael Steiner

The cochromatic number $ζ (G)$ of a graph $G$ is the smallest number of colors in a vertex-coloring of $G$ such that every color class forms an independent set or a clique. In three…