Daniel Gonçalves

collaborators

Showing math.COShow all

3 papers · 1 filter

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 $D$ can be augmented with (any num…

math.CO2024

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 su…

math.CO2024

Oriented trees in $O (k k)$ -chromatic digraphs, a subquadratic bound for Burr's conjecture

Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald

In 1980, Burr conjectured that every directed graph with chromatic number $2 k - 2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2…

Plane Strong Connectivity Augmentation

Brooks-type colourings of digraphs in linear time

Oriented trees in O(kk​)-chromatic digraphs, a subquadratic bound for Burr's conjecture

Oriented trees in $O (k k)$ -chromatic digraphs, a subquadratic bound for Burr's conjecture