2 papers
math.CO2025
Plane Strong Connectivity Augmentation
Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald +1
We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph can be augmented with (any num…
math.CO2025
Brooks-type colourings of digraphs in linear time
Daniel Gonçalves, Lucas Picasarri-Arrieta, Amadeus Reinald
Brooks' Theorem is a fundamental result on graph colouring, stating that the chromatic number of a graph is almost always upper bounded by its maximal degree. Lovász showed that s…