Publications (20)
On Minimum Connecting Transition Sets in Graphs
Thomas Bellitto, Benjamin Bergougnoux
A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the g…
On DP-Coloring of Digraphs
Jørgen Bang-Jensen, Thomas Bellitto, Thomas Schweser +1
DP-coloring is a relatively new coloring concept by DvoÅák and Postle and was introduced as an extension of list-colorings of (undirected) graphs. It transforms the problem of fi…
Proper-walk connection number of graphs
Jørgen Bang-Jensen, Thomas Bellitto, Anders Yeo
This paper studies the problem of proper-walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there e…
Canadian Traveller Problems in Temporal Graphs
Thomas Bellitto, Johanne Cohen, Bruno Escoffier +2
This paper formalises the Canadian Traveller problem as a positional two-player game on graphs. We consider two variants depending on whether an edge is blocked. In the locally-inf…
Locating Dominating Sets in local tournaments
Thomas Bellitto, Caroline Brosse, Benjamin Lévêque +1
A dominating set in a directed graph is a set of vertices such that all the vertices that do not belong to have an in-neighbour in . A locating set is a set of verti…
Close relatives (of Feedback Vertex Set), revisited
Hugo Jacob, Thomas Bellitto, Oscar Defrain +1
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a $2^{o(k \log k)} \cdo…