7 citations · 11 across the 11 of their papers we have counts for
4 papers · 1 filter
On cuts of small chromatic number in sparse graphs
Guillaume Aubian, Marthe Bonamy, Romain Bourneuf +2
For a given integer , let denote the supremum such that every sufficiently large graph with average degree less than admits a separator $X \subseteq…
A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
Romain Bourneuf, Tim Planken
The block-cut tree decomposes a connected graph along its cutvertices, displaying its 2-connected components. The Tutte-decomposition extends this idea to 2-separators in 2-connect…
A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Romain Bourneuf, Julien Cocquet, Chaoliang Tang +1
As shown by Robertson and Seymour, deciding whether the complete graph is a minor of an input graph is a fixed parameter tractable problem when parameterized by . From…
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 is a finite set of points of such that for each the ball intersects…