Showing 2024Show all
3 papers · 1 filter
math.CO2024
Fractional chromatic number vs. Hall ratio
Raphael Steiner
Given a graph , its Hall ratio forms a natural lower bound on its fractional chromatic number . 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 , an integer 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 of a graph is the smallest number of colors in a vertex-coloring of such that every color class forms an independent set or a clique. In three…