2 papers
math.CO2026
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.CO2025
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 has an independent set of size at least , where denote…