4 papers
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…
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…
Oriented trees in -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 contains any oriented tree of order as a subdigraph. Burr showed that chromatic number $(k-1)^2…
Two floor building needing eight colors
Stéphane Bessy, Daniel Gonçalves, Jean-Sébastien Sereni
Motivated by frequency assignment in office blocks, we study the chromatic number of the adjacency graph of -dimensional parallelepiped arrangements. In the case each parallelep…