Romain Bourneuf

activity

20222026

most citedA tamed family of triangle-free graphs with unbounded chromatic number

2 citations · 2 across the 8 of their papers we have counts for

collaborators

Showing cs.DMShow all

4 papers · 1 filter

cs.DM2026

Ramsey Obstructions to Disambiguation

Romain Bourneuf, Antonin Kiladjian, Stéphan Thomassé

A partial matrix has entries in ${0, 1, ⋆}$ , and a disambiguation replaces each $⋆$ by $0$ or $1$ . We construct partial matrices whose fully specified submatrices satisfy s…

cs.DM2026

Sample compression schemes for balls in structurally sparse graphs

Romain Bourneuf, Jędrzej Hodor, Piotr Micek +1

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. In a sample compression scheme, we…

cs.DM2025

A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number

Romain Bourneuf, Pierre Charbit, Stéphan Thomassé

In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if $V$ is a finite set of points of $R^{N}$ such that for each $v \in V$ the ball $B (v, 1)$ intersects…

cs.DM2023

Bounded twin-width graphs are polynomially $χ$ -bounded

Romain Bourneuf, Stéphan Thomassé

We show that every graph with twin-width $t$ has chromatic number $O (ω^{k_{t}})$ for some integer $k_{t}$ , where $ω$ denotes the clique number. This extends a quasi-polynomial bound fr…

Ramsey Obstructions to Disambiguation

Sample compression schemes for balls in structurally sparse graphs

A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number

Bounded twin-width graphs are polynomially χ-bounded

Bounded twin-width graphs are polynomially $χ$ -bounded