Logo

Oscar Defrain

 oscar.defrain@lis-lab.fr

Publications

Here is the exhaustive list of publications I co-authored. Every paper can either be found on arXiv or directly in PDF below; see also my dblp and Google scholar entries which should be fairly up to date. Journal Conference Preprint

Group entries:

    2025

  • Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney Enumerating minimal solution sets for metric graph problems Algorithmica 87(5): 712–735 (2025)
  • Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes Enumerating minimal dominating sets and variants in chordal bipartite graphs To appear in WADS 2025
  • Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin On the enumeration of signatures of XOR-CNF’s To appear in WADS 2025
  • Basile Couëtoux, Oscar Defrain, and Jean-Florent Raymond A quasi-optimal upper bound for induced paths in sparse graphs arXiv: abs/2507.22509 (2025)
  • Oscar Defrain, Arthur Ohana, and Simon Vilmin Translating between the representations of an acyclic convex geometry of bounded degree arXiv: abs/2506.24052 (2025)
  • Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes Enumerating minimal dominating sets and variants in chordal bipartite graphs arXiv: abs/2502.14611 (2025)
  • Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, and Prafullkumar Tale Parameterized complexity of isometric path partition: treewidth and diameter arXiv: abs/2508.05448 (2025)

    • 2024

  • Oscar Defrain, and Jean-Florent Raymond Sparse graphs without long induced paths Journal of Combinatorial Theory, Series B 166: 30–49 (2024)
  • Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, and Kunihiro Wasa On the hardness of inclusion-wise minimal separators enumeration Information Processing Letters 185: 106469 (2024)
  • Oscar Defrain, Antonio E. Porreca, and Ekaterina Timofeeva Polynomial-delay generation of functional digraphs up to isomorphism Discrete Applied Mathematics 357: 24–33 (2024)
  • Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney Enumerating minimal solution sets for metric graph problems WG 2024: 50–64
  • Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension IWOCA 2024: 111–125
  • Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond Local certification of geometric graph classes MFCS 2024: 48:1–48:14
  • Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin On the enumeration of signatures of XOR-CNF’s arXiv: abs/2402.18537 (2024)
  • Oscar Defrain, Antonio E. Porreca, and Ekaterina Timofeeva Polynomial-delay generation of functional digraphs up to isomorphism arXiv: abs/2302.13832 (2024)

    • 2023

  • Marthe Bonamy, Oscar Defrain, Tereza Klimosová, Aurélie Lagoutte, and Jonathan Narboni On Vizing’s edge colouring question Journal of Combinatorial Theory, Series B 159: 126–139 (2023)
  • Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly Discrete Mathematics & Theoretical Computer Science 25(2) (2023)
  • Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney Enumerating minimal solution sets for metric graph problems arXiv: abs/2309.17419 (2023)
  • Oscar Defrain, and Jean-Florent Raymond Sparse graphs without long induced paths arXiv: abs/2304.09679 (2023)
  • Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, and Kunihiro Wasa On the hardness of inclusion-wise minimal separators enumeration arXiv: abs/2308.15444 (2023)
  • Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension arXiv: abs/2305.06974 (2023)
  • Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond Local certification of geometric graph classes arXiv: abs/2311.16953 (2023)

    • 2022

  • Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, and Michał Pilipczuk On objects dual to tree-cut decompositions Journal of Combinatorial Theory, Series B 157: 401–428 (2022)
  • Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, and Michał Pilipczuk On digraphs without onion star immersions arXiv: abs/2211.15477 (2022)

    • 2021

  • Oscar Defrain, Lhouari Nourine, and Takeaki Uno On the dualization in distributive lattices and related problems Discrete Applied Mathematics 300: 85–96 (2021)
  • Oscar Defrain, Lhouari Nourine, and Simon Vilmin Translating between the representations of a ranked convex geometry Discrete Mathematics 344(7): 112399 (2021)
  • Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk Close Relatives (Of Feedback Vertex Set), Revisited IPEC 2021: 21:1–21:15
  • Marthe Bonamy, Oscar Defrain, Tereza Klimosová, Aurélie Lagoutte, and Jonathan Narboni On Vizing’s edge colouring question arXiv: abs/2107.07900 (2021)
  • Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, and Michał Pilipczuk On objects dual to tree-cut decompositions arXiv: abs/2103.14667 (2021)
  • Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk Close Relatives (Of Feedback Vertex Set), Revisited arXiv: abs/2106.16015 (2021)
  • Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly arXiv: abs/2110.14003 (2021)

    • 2020

  • Marthe Bonamy, Pierre Charbit, Oscar Defrain, Gwenaël Joret, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor, and Jean-Sébastien Sereni Revisiting a Theorem by Folkman on Graph Colouring Electronic Journal of Combinatorics 27(1): 1 (2020)
  • Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut Avoidable Paths in Graphs Electronic Journal of Combinatorics 27(4): 4 (2020)
  • Oscar Defrain, and Lhouari Nourine Dualization in lattices given by implicational bases Theoretical Computer Science 814: 169–176 (2020)
  • Marthe Bonamy, Oscar Defrain, Marc Heinrich, Michał Pilipczuk, and Jean-Florent Raymond Enumerating Minimal Dominating Sets in $K_t$-free Graphs and Variants ACM Transactions on Algorithms 16(3): 39:1–39:23 (2020)
  • Marthe Bonamy, Oscar Defrain, Piotr Micek, and Lhouari Nourine Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets arXiv: abs/2004.07214 (2020)

    • 2019

  • Oscar Defrain, and Lhouari Nourine Dualization in lattices given by implicational bases ICFCA 2019: 89–98
  • Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond Enumerating Minimal Dominating Sets in Triangle-free Graphs STACS 2019: 16:1–16:12
  • Oscar Defrain, and Lhouari Nourine Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in $P_7$-Free and $P_8$-Free Chordal Graphs ISAAC 2019: 63:1–63:16
  • Oscar Defrain, Lhouari Nourine, and Takeaki Uno On the dualization in distributive lattices and related problems arXiv: abs/1902.07004 (2019)
  • Oscar Defrain, Lhouari Nourine, and Simon Vilmin Translating between the representations of a ranked convex geometry arXiv: abs/1907.09433 (2019)
  • Marthe Bonamy, Pierre Charbit, Oscar Defrain, Gwenaël Joret, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor, and Jean-Sébastien Sereni Revisiting a Theorem by Folkman on Graph Colouring arXiv: abs/1907.11429 (2019)
  • Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut Avoidable Paths in Graphs arXiv: abs/1908.03788 (2019)
  • Oscar Defrain, and Lhouari Nourine Dualization in lattices given by implicational bases arXiv: abs/1901.07503 (2019)

    • 2018

  • Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond Enumerating Minimal Dominating Sets in Triangle-free Graphs arXiv: abs/1810.00789 (2018)
  • Oscar Defrain, and Lhouari Nourine Neighborhood preferences for minimal dominating sets enumeration arXiv: abs/1805.02412 (2018)

    • 2017

  • Oscar Defrain, Bruno Durand, and Grégory Lafitte Infinite Time Busy Beavers CiE 2017: 221–233