1 citations · 2 across the 16 of their papers we have counts for
7 papers · 1 filter
Generating minimal redundant and maximal irredundant sets in incidence graphs
Emanuel Castelo, Jérémie Chalopin, Oscar Defrain +1
It has been proved by Boros and Makino that there is no output-polynomial-time algorithm enumerating the minimal redundant sets or the maximal irredundant sets of a hypergraph, unl…
A quasi-optimal upper bound for induced paths in sparse graphs
Basile Couëtoux, Oscar Defrain, Jean-Florent Raymond
In 2012, Nešetřil and Ossona de Mendez proved that graphs of bounded degeneracy that have a path of order also have an induced path of order . In this paper we…
Sparse graphs without long induced paths
Oscar Defrain, Jean-Florent Raymond
Graphs of bounded degeneracy are known to contain induced paths of order when they contain a path of order , as proved by Nešetřil and Ossona de Mendez (2012).…
On digraphs without onion star immersions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
The -onion star is the digraph obtained from a star with leaves by replacing every edge by a triple of arcs, where in triples we orient two arcs away from the center, a…
On Vizing's edge colouring question
Marthe Bonamy, Oscar Defrain, Tereza Klimošová +2
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a se…
On objects dual to tree-cut decompositions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
Tree-cut width is a graph parameter introduced by Wollan that is an analogue of treewidth for the immersion order on graphs in the following sense: the tree-cut width of a graph is…
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain +5
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference…