Robin Petit

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2026

An improved bound on the treewidth of planar graphs excluding a grid minor

Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret +3

We show that every planar graph with no $t \times t$ grid minor has treewidth at most $4 t + 4$ . This improves on the previously best known bound of $\frac{9}{2} t - \frac{11}{2}$ , du…

math.CO2024

Computing the degreewidth of a digraph is hard

Pierre Aboulker, Nacim Oijid, Robin Petit +2

Given a digraph, an ordering of its vertices defines a backedge graph, namely the undirected graph whose edges correspond to the arcs pointing backwards with respect to the order.…

math.CO2024

A Caro-Wei bound for induced linear forests in graphs

Gwenaël Joret, Robin Petit

A well-known result due to Caro (1979) and Wei (1981) states that every graph $G$ has an independent set of size at least $\sum_{v \in V (G)} \frac{1}{d ( v ) + 1}$ , where $d (v)$ denote…