9 papers
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…
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…
Avoidable paths in graphs
Marthe Bonamy, Oscar Defrain, Meike Hatzel +1
We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises th…
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…
Translating between the representations of a ranked convex geometry
Oscar Defrain, Lhouari Nourine, Simon Vilmin
It is well known that every closure system can be represented by an implicational base, or by the set of its meet-irreducible elements. In Horn logic, these are respectively known…
On the dualization in distributive lattices and related problems
Oscar Defrain, Lhouari Nourine, Takeaki Uno
In this paper, we study the dualization in distributive lattices, a generalization of the well-known hypergraph dualization problem. We in particular propose equivalent formulation…