Raphael Steiner

activity

20242026

collaborators

5 papers

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…