1 citations · 2 across the 16 of their papers we have counts for
5 papers · 1 filter
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…
Dualization in lattices given by implicational bases
Oscar Defrain, Lhouari Nourine
It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P=NP. In this paper, we~show that this result ho…