Logo

Oscar Defrain

 oscar.defrain@lis-lab.fr

Powered by Jekyll—theme by BDHU. Something wrong? Please contact Oscar Defrain.

Last updated: October 2023.

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. 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
  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. To appear in Discret. Math. Theor. Comput. Sci. (2024)
  3. Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, and Kunihiro Wasa. On the hardness of inclusion-wise minimal separators enumeration. Inf. Process. Lett. 185: 106469 (2024) DOI
  4. 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

2023

  1. Marthe Bonamy, Oscar Defrain, Tereza Klimosová, Aurélie Lagoutte, and Jonathan Narboni. On Vizing’s edge colouring question. J. Comb. Theory, Ser. 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. J. Comb. Theory, Ser. 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. Discret. Appl. Math. 300: 85–96 (2021) DOI arXiv
  2. Oscar Defrain, Lhouari Nourine, and Simon Vilmin. Translating between the representations of a ranked convex geometry. Discret. Math. 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. Electron. J. Comb. 27, 1: 1 (2020) DOI arXiv
  3. Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut. Avoidable Paths in Graphs. Electron. J. Comb. 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 Trans. Algorithms 16, 3: 39:1–39:23 (2020) DOI arXiv
  5. Oscar Defrain and Lhouari Nourine. Dualization in lattices given by implicational bases. Theor. Comput. Sci. 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. Formal Concept Analysis - 15th International Conference, ICFCA 2019, Frankfurt, Germany, June 25-28, 2019, Proceedings, Springer, 89–98 (2019) DOI arXiv
  2. 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. 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 63:1–63:16 (2019) DOI arXiv
  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, March 13-16, 2019, Berlin, Germany, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16:1–16:12 (2019) DOI arXiv
  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, Turku, Finland, June 12-16, 2017, Proceedings, Springer, 221–233 (2017)   DOI