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 Thesis

2024

  1. Oscar Defrain and Jean-Florent Raymond. Sparse graphs without long induced paths. Journal of Combinatorial Theory, Series B 166: 30–49 (2024) DOI arXiv
  2. 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 (2024) DOI arXiv
  3. 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) DOI arXiv
  4. Oscar Defrain, Antonio E. Porreca, and Ekaterina Timofeeva. Polynomial-delay generation of functional digraphs up to isomorphism. Discrete Applied Mathematics 357: 24–33 (2024) DOI arXiv
  5. Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney. Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension. To appear in International Workshop on Combinatorial Algorithms, IWOCA 2024 (2024) arXiv
  6. Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney. Enumerating minimal solution sets for metric graph problems. To appear in Graph-Theoretic Concepts in Computer Science, WG 2024 (2024) arXiv
  7. Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local certification of geometric graph classes. To appear in International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 (2024) arXiv
  8. Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin. On the enumeration of signatures of XOR-CNF’s. CoRR abs/2402.18537 (2024) arXiv
  9. Oscar Defrain, Antonio E. Porreca, and Ekaterina Timofeeva. Polynomial-delay generation of functional digraphs up to isomorphism. CoRR abs/2302.13832 (2024) arXiv

2023

  1. 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) DOI arXiv
  2. Oscar Defrain and Jean-Florent Raymond. Sparse graphs without long induced paths. CoRR abs/2304.09679 (2023) arXiv
  3. Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney. Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension. CoRR abs/2305.06974 (2023) arXiv
  4. Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, and Kunihiro Wasa. On the hardness of inclusion-wise minimal separators enumeration. CoRR abs/2308.15444 (2023) arXiv
  5. Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney. Enumerating minimal solution sets for metric graph problems. CoRR abs/2309.17419 (2023) arXiv
  6. Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local certification of geometric graph classes. CoRR abs/2311.16953 (2023) arXiv

2022

  1. Ł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) DOI arXiv
  2. Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, and Michał Pilipczuk. On digraphs without onion star immersions. CoRR abs/2211.15477 (2022) arXiv

2021

  1. Oscar Defrain, Lhouari Nourine, and Takeaki Uno. On the dualization in distributive lattices and related problems. Discrete Applied Mathematics 300: 85–96 (2021) DOI arXiv
  2. Oscar Defrain, Lhouari Nourine, and Simon Vilmin. Translating between the representations of a ranked convex geometry. Discrete Mathematics 344, 7: 112399 (2021) DOI arXiv
  3. Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close Relatives (Of Feedback Vertex Set), Revisited. 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lisbon, Portugal, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 21:1–21:15 (2021) DOI arXiv
  4. Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, and Michał Pilipczuk. On objects dual to tree-cut decompositions. CoRR abs/2103.14667 (2021) arXiv
  5. Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close relatives (of Feedback Vertex Set), revisited. CoRR abs/2106.16015 (2021) arXiv
  6. Marthe Bonamy, Oscar Defrain, Tereza Klimosová, Aurélie Lagoutte, and Jonathan Narboni. On Vizing’s edge colouring question. CoRR abs/2107.07900 (2021) arXiv
  7. 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. CoRR abs/2110.14003 (2021) arXiv

2020

  1. Oscar Defrain. On the dualization problem in graphs, hypergraphs, and lattices. (Sur le problème de dualisation dans les graphes, hypergraphes, et treillis). Retrieved from archives-ouvertes.fr/tel-03036782 (2020)
  2. 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) DOI arXiv
  3. Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut. Avoidable Paths in Graphs. Electronic Journal of Combinatorics 27, 4: 4 (2020) DOI arXiv
  4. Marthe Bonamy, Oscar Defrain, Marc Heinrich, Michał Pilipczuk, and Jean-Florent Raymond. Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants. ACM Transactions on Algorithms 16, 3: 39:1–39:23 (2020) DOI arXiv
  5. Oscar Defrain and Lhouari Nourine. Dualization in lattices given by implicational bases. Theoretical Computer Science 814: 169–176 (2020) DOI arXiv
  6. Marthe Bonamy, Oscar Defrain, Piotr Micek, and Lhouari Nourine. Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets. CoRR abs/2004.07214 (2020) arXiv

2019

  1. Oscar Defrain and Lhouari Nourine. Dualization in Lattices Given by Implicational Bases. International Conference on Formal Concept Analysis, ICFCA 2019, Springer, 89–98 (2019)
  2. 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. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 63:1–63:16 (2019)
  3. Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond. Enumerating minimal dominating sets in triangle-free graphs. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 16:1–16:12 (2019)
  4. 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. CoRR abs/1907.11429 (2019) arXiv
  5. Oscar Defrain and Lhouari Nourine. Dualization in lattices given by implicational bases. CoRR abs/1901.07503 (2019) arXiv
  6. Oscar Defrain, Lhouari Nourine, and Takeaki Uno. On the dualization in distributive lattices and related problems. CoRR abs/1902.07004 (2019) arXiv
  7. Oscar Defrain, Lhouari Nourine, and Simon Vilmin. Translating between the representations of a ranked convex geometry. CoRR abs/1907.09433 (2019) arXiv
  8. Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut. Avoidable paths in graphs. CoRR abs/1908.03788 (2019) arXiv

2018

  1. Oscar Defrain and Lhouari Nourine. Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P\(_\mbox7\)-Free and P\(_\mbox8\)-Free Chordal Graphs. CoRR abs/1805.02412 (2018) arXiv
  2. Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond. Enumerating minimal dominating sets in triangle-free graphs. CoRR abs/1810.00789 (2018) arXiv

2017

  1. Oscar Defrain, Bruno Durand, and Grégory Lafitte. Infinite Time Busy Beavers. Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, (CiE 2017), Springer, 221–233 (2017)