2024
Journal articles
- auteur
- Jørgen Bang-Jensen, Stéphane Bessy, Lucas Picasarri-Arrieta
- titre
- Constrained Flows in Networks
- article
- Theoretical Computer Science, 2024, 1010, pp.114702. ⟨10.1016/j.tcs.2024.114702⟩
- DOI
- DOI : 10.1016/j.tcs.2024.114702
- Accès au bibtex
-
- auteur
- Edouard Bonnet, Dibyayan Chakraborty, Julien Duron
- titre
- Cutting Barnette graphs perfectly is hard
- article
- Theoretical Computer Science, 2024, 1010 (114701), ⟨https://doi.org/10.1016/j.tcs.2024.114701⟩
- DOI
- DOI : https://doi.org/10.1016/j.tcs.2024.114701
- Accès au texte intégral et bibtex
-
- auteur
- Peter Borg, Carl Feghali, Rémi Pellerin
- titre
- Solution to a problem of Katona on counting cliques of weighted graphs
- article
- Discrete Applied Mathematics, 2024, 345, pp.147-155. ⟨10.1016/j.dam.2023.11.028⟩
- DOI
- DOI : 10.1016/j.dam.2023.11.028
- Accès au bibtex
-
- auteur
- Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Amadeus Reinald
- titre
- Digraph redicolouring
- article
- European Journal of Combinatorics, 2024, 116, pp.103876. ⟨10.1016/j.ejc.2023.103876⟩
- DOI
- DOI : 10.1016/j.ejc.2023.103876
- Accès au texte intégral et bibtex
-
- auteur
- Dibyayan Chakraborty, Carl Feghali, Reem Mahmoud
- titre
- Kempe equivalent list colorings revisited
- article
- Journal of Graph Theory, 2024, ⟨10.1002/jgt.23142⟩
- DOI
- DOI : 10.1002/jgt.23142
- Accès au bibtex
-
- auteur
- Linda Cook, Jake Horsfield, Myriam Preissmann, Cléophée Robin, Paul Seymour, Ni Luh Dewi Sintiari, Nicolas Trotignon, Kristina Vušković
- titre
- Graphs with all holes the same length
- article
- Journal of Combinatorial Theory, Series B, 2024, 168, pp.96-158. ⟨10.1016/j.jctb.2024.04.006⟩
- DOI
- DOI : 10.1016/j.jctb.2024.04.006
- Accès au bibtex
-
- auteur
- Jonas Costa Ferreira da Silva, Frédéric Havet
- titre
- On b-greedy colourings and z-colourings
- article
- Discrete Applied Mathematics, 2024, 359, pp.250-268. ⟨10.1016/j.dam.2024.08.001⟩
- DOI
- DOI : 10.1016/j.dam.2024.08.001
- Accès au texte intégral et bibtex
-
- auteur
- Daniel Cranston, Carl Feghali
- titre
- Kempe classes and almost bipartite graphs
- article
- Discrete Applied Mathematics, 2024, 357, pp.94-98. ⟨10.1016/j.dam.2024.05.043⟩
- DOI
- DOI : 10.1016/j.dam.2024.05.043
- Accès au bibtex
-
- auteur
- Christophe Crespelle, Rémi Pellerin, Stéphan Thomassé
- titre
- A quasi-quadratic vertex-kernel for Cograph Edge Editing
- article
- Discrete Applied Mathematics, 2024, 357, pp.282-296. ⟨10.1016/j.dam.2024.05.014⟩
- DOI
- DOI : 10.1016/j.dam.2024.05.014
- Accès au bibtex
-
- auteur
- Zdeněk Dvořák, Carl Feghali
- titre
- Solution to a Problem of Grünbaum on the Edge Density of 4-Critical Planar Graphs
- article
- Combinatorica, 2024, ⟨10.1007/s00493-024-00100-8⟩
- DOI
- DOI : 10.1007/s00493-024-00100-8
- Accès au bibtex
-
- auteur
- Carl Feghali, Malory Marin
- titre
- Three remarks on W graphs
- article
- Theoretical Computer Science, 2024, 990, pp.114403. ⟨10.1016/j.tcs.2024.114403⟩
- DOI
- DOI : 10.1016/j.tcs.2024.114403
- Accès au bibtex
-
- auteur
- Carl Feghali, Robert Šámal
- titre
- Decomposing a triangle-free planar graph into a forest and a subcubic forest
- article
- European Journal of Combinatorics, 2024, 116, pp.103878. ⟨10.1016/j.ejc.2023.103878⟩
- DOI
- DOI : 10.1016/j.ejc.2023.103878
- Accès au bibtex
-
- auteur
- Carl Feghali
- titre
- Dirac’s theorem on chordal graphs implies Brooks’ theorem
- article
- Discrete Mathematics, 2024, 347 (3), pp.113791. ⟨10.1016/j.disc.2023.113791⟩
- DOI
- DOI : 10.1016/j.disc.2023.113791
- Accès au bibtex
-
- auteur
- Emeric Gioan, Michel Las Vergnas
- titre
- Computing the fully optimal spanning tree of an ordered bipolar directed graph
- article
- Discrete Mathematics, 2024, 347 (5), pp.113895
- Accès au texte intégral et bibtex
-
- auteur
- Frédéric Havet, Lucas Picasarri-Arrieta, Clément Rambaud
- titre
- On the minimum number of arcs in 4-dicritical oriented graphs
- article
- Journal of Graph Theory, 2024, 107 (4), pp.778-809. ⟨10.1002/jgt.23159⟩
- DOI
- DOI : 10.1002/jgt.23159
- Accès au texte intégral et bibtex
-
- auteur
- Gwenaël Joret, Clément Rambaud
- titre
- Neighborhood complexity of planar graphs
- article
- Combinatorica, 2024, 44 (5), pp.1115-1148. ⟨10.1007/s00493-024-00110-6⟩
- DOI
- DOI : 10.1007/s00493-024-00110-6
- Accès au texte intégral et bibtex
-
- auteur
- Nicolas Nisse, Lucas Picasarri-Arrieta, Ignasi Sau
- titre
- Redicolouring digraphs: directed treewidth and cycle-degeneracy
- article
- Discrete Applied Mathematics, 2024, 356, pp.191-208. ⟨10.1016/j.dam.2024.05.042⟩
- DOI
- DOI : 10.1016/j.dam.2024.05.042
- Accès au texte intégral et bibtex
-
- auteur
- Lucas Picasarri-Arrieta, Clément Rambaud
- titre
- Subdivisions in dicritical digraphs with large order or digirth
- article
- European Journal of Combinatorics, 2024, 122, pp.104022. ⟨10.1016/j.ejc.2024.104022⟩
- DOI
- DOI : 10.1016/j.ejc.2024.104022
- Accès au texte intégral et bibtex
-
- auteur
- Lucas Picasarri-Arrieta, Michael Stiebitz
- titre
- Minimum number of arcs in $k$-critical digraphs with order at most k-1$
- article
- Discrete Mathematics, 2024, 347 (9), pp.114072. ⟨10.1016/j.disc.2024.114072⟩
- DOI
- DOI : 10.1016/j.disc.2024.114072
- Accès au bibtex
-
- auteur
- Pegah Pournajafi, Nicolas Trotignon
- titre
- Burling graphs revisited, part II: Structure
- article
- European Journal of Combinatorics, 2024, 116, pp.103849. ⟨10.1016/j.ejc.2023.103849.⟩
- DOI
- DOI : 10.1016/j.ejc.2023.103849.
- Accès au bibtex
-
- auteur
- Pegah Pournajafi, Nicolas Trotignon
- titre
- Burling graphs revisited, part III: Applications to χ -boundedness
- article
- European Journal of Combinatorics, 2024, 116, pp.103850. ⟨10.1016/j.ejc.2023.103850⟩
- DOI
- DOI : 10.1016/j.ejc.2023.103850
- Accès au bibtex
-
Conference papers
- auteur
- Stéphane Bessy, Stéphan Thomassé, Laurent Viennot
- titre
- Temporalizing Digraphs via Linear-Size Balanced Bi-Trees
- article
- STACS 2024 – 41st International Symposium on Theoretical Aspects of Computer Science, Mar 2024, Clermont-Ferrand, France. pp.13:1-13:12, ⟨10.4230/LIPIcs.STACS.2024.13⟩
- DOI
- DOI : 10.4230/LIPIcs.STACS.2024.13
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé
- titre
- Factoring Pattern-Free Permutations into Separable ones
- article
- SODA 2024, Jan 2024, Alexandria, United States
- Accès au texte intégral et bibtex
-
- auteur
- Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, Nicolas Trotignon
- titre
- Detecting $K_{2,3}$ as an Induced Minor
- article
- IWOCA 2024, Jul 2024, Ischia, Italy. pp.151-164, ⟨10.1007/978-3-031-63021-7_12⟩
- DOI
- DOI : 10.1007/978-3-031-63021-7_12
- Accès au bibtex
-
Reports
- auteur
- Caroline Brosse, Nicolas Martins, Nicolas Nisse, Rudini Sampaio
- titre
- The Convex Set Forming Game
- article
- Inria. 2024
- Accès au texte intégral et bibtex
-
Theses
- auteur
- Lucas Picasarri-Arrieta
- titre
- Digraph colouring
- article
- Combinatorics [math.CO]. Université Côte d’Azur, 2024. English. ⟨NNT : 2024COAZ4023⟩
- Accès au texte intégral et bibtex
-
Preprints, Working Papers, …
- auteur
- Édouard Bonnet, Carl Feghali, Tung Nguyen, Alex Scott, Paul Seymour, Stéphan Thomassé, Nicolas Trotignon
- titre
- Graphs without a 3-connected subgraph are 4-colourable
- article
- 2024
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev
- titre
- Adjacency Labeling Schemes for Small Classes
- article
- 2024
- Accès au texte intégral et bibtex
-
- auteur
- Lech Duraj, Ross J. Kang, Hoang La, Jonathan Narboni, Filip Pokrývka, Clément Rambaud, Amadeus Reinald
- titre
- The $\chi$-binding function of $d$-directional segment graphs
- article
- 2024
- Accès au bibtex
-
- auteur
- Daniel Gonçalves, Lucas Picasarri-Arrieta, Amadeus Reinald
- titre
- Brooks-type colourings of digraphs in linear time
- article
- 2024
- Accès au texte intégral et bibtex
-
- auteur
- Frédéric Havet, Florian Hörsch, Lucas Picasarri-Arrieta
- titre
- The 3-dicritical semi-complete digraphs
- article
- 2024
- Accès au texte intégral et bibtex
-
- auteur
- Florian Hörsch, Lucas Picasarri-Arrieta
- titre
- Complexity results on the decomposition of a digraph into directed linear forests and out-stars
- article
- 2024
- Accès au texte intégral et bibtex
-
- auteur
- Ken-Ichi Kawarabayashi, Lucas Picasarri-Arrieta
- titre
- An analogue of Reed’s conjecture for digraphs
- article
- 2024
- Accès au texte intégral et bibtex
-
2023
Journal articles
- auteur
- Ali Al Zoobi, David Coudert, Nicolas Nisse
- titre
- Finding the k Shortest Simple Paths: Time and Space trade-offs
- article
- ACM Journal of Experimental Algorithmics, 2023, 28, pp.23. ⟨10.1145/3626567⟩
- DOI
- DOI : 10.1145/3626567
- Accès au texte intégral et bibtex
-
- auteur
- Julio Araujo, Julien Bensmail, Victor Campos, Frédéric Havet, Ana Karolinna Maia, Nicolas Nisse, Ana Silva
- titre
- On Finding the Best and Worst Orientations for the Metric Dimension
- article
- Algorithmica, 2023, 85 (10), pp.2962-3002. ⟨10.1007/s00453-023-01132-0⟩
- DOI
- DOI : 10.1007/s00453-023-01132-0
- Accès au texte intégral et bibtex
-
- auteur
- Valentin Bartier, Nicolas Bousquet, Carl Feghali, Marc Heinrich, Benjamin Moore, Théo Pierron
- titre
- Recoloring Planar Graphs of Girth at Least Five
- article
- SIAM Journal on Discrete Mathematics, 2023, 37 (1), pp.332-350. ⟨10.1137/21M1463598⟩
- DOI
- DOI : 10.1137/21M1463598
- Accès au bibtex
-
- auteur
- Pierre Bergé, Anthony Busson, Carl Feghali, Rémi Watrigant
- titre
- 1-Extendability of Independent Sets
- article
- Algorithmica, 2023, 86 (3), pp.757-781. ⟨10.1007/s00453-023-01138-8⟩
- DOI
- DOI : 10.1007/s00453-023-01138-8
- Accès au bibtex
-
- auteur
- Jean-Claude Bermond, Takako Kodate, Joseph Yu
- titre
- Gossiping with interference in radio ring networks
- article
- Discrete Mathematics and Theoretical Computer Science, 2023, 25 (2), pp.#5. ⟨10.46298/dmtcs.9399⟩
- DOI
- DOI : 10.46298/dmtcs.9399
- Accès au texte intégral et bibtex
-
- auteur
- Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta, Dieter Rautenbach
- titre
- Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs
- article
- The Electronic Journal of Combinatorics, 2023, 30 (1), pp.1-35. ⟨10.37236/10866⟩
- DOI
- DOI : 10.37236/10866
- Accès au texte intégral et bibtex
-
- auteur
- Edouard Bonnet, Hugues Déprés
- titre
- Twin-width can be exponential in treewidth
- article
- Journal of Combinatorial Theory, Series B, 2023
- Accès au texte intégral et bibtex
-
- auteur
- Cláudio Carvalho, Jonas Costa, Raul Lopes, Ana Karolinna Maia, Nicolas Nisse, Cláudia Linhares Sales
- titre
- From branchings to flows: a study of an Edmonds’ like property to arc-disjoint branching flows
- article
- Discrete Mathematics and Theoretical Computer Science, In press, vol. 25:1 (10), pp.15. ⟨10.46298/dmtcs.9302⟩
- DOI
- DOI : 10.46298/dmtcs.9302
- Accès au texte intégral et bibtex
-
- auteur
- Timothée Corsini, Quentin Deschamps, Carl Feghali, Daniel Gonçalves, Hélène Langlois, Alexandre Talon
- titre
- Partitioning into degenerate graphs in linear time
- article
- European Journal of Combinatorics, 2023, 114, pp.103771. ⟨10.1016/j.ejc.2023.103771⟩
- DOI
- DOI : 10.1016/j.ejc.2023.103771
- Accès au bibtex
-
- auteur
- Quentin Deschamps, Carl Feghali, František Kardoš, Clément Legrand-Duchesne, Théo Pierron
- titre
- Strengthening a theorem of Meyniel
- article
- SIAM Journal on Discrete Mathematics, 2023, 37 (2), ⟨10.1137/22M1474394⟩
- DOI
- DOI : 10.1137/22M1474394
- Accès au texte intégral et bibtex
-
- auteur
- Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
- titre
- Treelength of series–parallel graphs
- article
- Discrete Applied Mathematics, 2023, 341, pp.16-30. ⟨10.1016/j.dam.2023.07.022⟩
- DOI
- DOI : 10.1016/j.dam.2023.07.022
- Accès au texte intégral et bibtex
-
- auteur
- Carl Feghali
- titre
- Another Proof of Euler’s Circuit Theorem
- article
- The American Mathematical Monthly, 2023, 131 (2), pp.164-164. ⟨10.1080/00029890.2023.2280361⟩
- DOI
- DOI : 10.1080/00029890.2023.2280361
- Accès au bibtex
-
- auteur
- Lucas Picasarri-Arrieta
- titre
- Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring
- article
- Journal of Graph Theory, 2023, ⟨10.1002/jgt.23066⟩
- DOI
- DOI : 10.1002/jgt.23066
- Accès au texte intégral et bibtex
-
Conference papers
- auteur
- Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Karol Suchan, Nicolas Nisse
- titre
- Semi-proper orientations of dense graphs
- article
- LAGOS 2023 6 XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023, Huatulco, Mexico. pp.231-240, ⟨10.1016/j.procs.2023.08.233⟩
- DOI
- DOI : 10.1016/j.procs.2023.08.233
- Accès au texte intégral et bibtex
-
- auteur
- Julien Bensmail, Victor Campos, Ana Karolinna Maia, Nicolas Nisse, Ana Silva
- titre
- Deciding the Erdős-Pósa property in 3-connected digraphs
- article
- WG 2023 – 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023, Fribourg (CH), Switzerland. pp.59-71, ⟨10.1007/978-3-031-43380-1_5⟩
- DOI
- DOI : 10.1007/978-3-031-43380-1_5
- Accès au texte intégral et bibtex
-
- auteur
- Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, Mathis Rocton
- titre
- PACE Solver Description: Touiouidth
- article
- IPEC 2023 – 18th International Symposium on Parameterized and Exact Computation, Sep 2023, Amsterdam, Netherlands. pp.4, ⟨10.4230/LIPIcs.IPEC.2023.38⟩
- DOI
- DOI : 10.4230/LIPIcs.IPEC.2023.38
- Accès au texte intégral et bibtex
-
- auteur
- Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos, Sebastian Wiederrecht
- titre
- Kernelization for Graph Packing Problems via Rainbow Matching
- article
- SODA 2023 – 34th ACM/SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Jan 2023, Florence, Italy. pp.3654-3663, ⟨10.1137/1.9781611977554.ch139⟩
- DOI
- DOI : 10.1137/1.9781611977554.ch139
- Accès au texte intégral et bibtex
-
- auteur
- Edouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek
- titre
- Maximum Independent Set when excluding an induced minor: K_1 + tK_2 and tC_3 cup C_4
- article
- ESA 2023, Sep 2023, Amsterdam, Netherlands
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Julien Duron
- titre
- Stretch-width
- article
- IPEC 2023, Sep 2023, Amsterdam, Netherlands
- Accès au texte intégral et bibtex
-
- auteur
- Julien Duron, Frédéric Havet, Florian Hörsch, Clément Rambaud
- titre
- On the minimum number of inversions to make a digraph k-(arc-)strong
- article
- EUROCOMB 2023 – European Conference on Combinatorics, Graph Theory and Applications, Aug 2023, Prague, Czech Republic. pp.386-392, ⟨10.5817/CZ.MUNI.EUROCOMB23-054⟩
- DOI
- DOI : 10.5817/CZ.MUNI.EUROCOMB23-054
- Accès au texte intégral et bibtex
-
- auteur
- Carl Feghali, Felicia Lucke, Daniël Paulusma, Bernard Ries
- titre
- Matching Cuts in Graphs of High Girth and H-Free Graphs
- article
- ISAAC 2023, Dec 2023, Kyoto (Japan), Japan. ⟨10.4230/LIPIcs.ISAAC.2023.31⟩
- DOI
- DOI : 10.4230/LIPIcs.ISAAC.2023.31
- Accès au bibtex
-
- auteur
- Fedor Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi
- titre
- Lossy Kernelization for (Implicit) Hitting Set Problems
- article
- ESA 2023, Sep 2023, Amsterdam, Netherlands. ⟨10.4230/LIPIcs.ESA.2023.49⟩
- DOI
- DOI : 10.4230/LIPIcs.ESA.2023.49
- Accès au bibtex
-
- auteur
- Colin Geniet, Stéphan Thomassé
- titre
- First Order Logic and Twin-Width in Tournaments
- article
- 31st Annual European Symposium on Algorithms (ESA 2023), Sep 2023, Amsterdam, Netherlands. pp.53:1–53:14, ⟨10.4230/LIPIcs.ESA.2023.53⟩
- DOI
- DOI : 10.4230/LIPIcs.ESA.2023.53
- Accès au texte intégral et bibtex
-
- auteur
- Frédéric Havet, Lucas Picasarri-Arrieta, Clément Rambaud
- titre
- On the Minimum Number of Arcs in 4-Dicritical Oriented Graphs
- article
- WG 2023 – International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023, Fribourg, Switzerland. pp.376-387, ⟨10.1007/978-3-031-43380-1_27⟩
- DOI
- DOI : 10.1007/978-3-031-43380-1_27
- Accès au texte intégral et bibtex
-
- auteur
- Lucas Picasarri-Arrieta
- titre
- Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring
- article
- Eurocomb 2023 – 12th European Conference on Combinatorics, Graph Theory and Applications, Aug 2023, Prague, Czech Republic. pp.760-765, ⟨10.5817/CZ.MUNI.EUROCOMB23-105⟩
- DOI
- DOI : 10.5817/CZ.MUNI.EUROCOMB23-105
- Accès au texte intégral et bibtex
-
Reports
- auteur
- Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Amadeus Reinald
- titre
- Digraph redicolouring
- article
- Inria. 2023
- Accès au texte intégral et bibtex
-
Preprints, Working Papers, …
- auteur
- Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Stéphan Thomassé
- titre
- ( #» P 6 , triangle)-free digraphs have bounded dichromatic number
- article
- 2023
- Accès au texte intégral et bibtex
-
- auteur
- Pierre Aboulker, Thomas Bellitto, Frédéric Havet, Clément Rambaud, Clément Rambaud
- titre
- On the minimum number of arcs in k-dicritical oriented graphs
- article
- 2023
- Accès au texte intégral et bibtex
-
- auteur
- Stéphane Bessy, Frédéric Havet, Lucas Picasarri-Arrieta
- titre
- Dichromatic number of chordal graphs
- article
- 2023
- Accès au bibtex
-
- auteur
- Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, Kunihiro Wasa
- titre
- On the hardness of inclusion-wise minimal separators enumeration
- article
- 2023
- DOI
- DOI : 10.1016/j.ipl.2023.106469
- Accès au texte intégral et bibtex
-
2022
Journal articles
- auteur
- Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković
- titre
- Graphs with polynomially many minimal separators
- article
- Journal of Combinatorial Theory, Series B, 2022, 152, pp.248-280. ⟨10.1016/j.jctb.2021.10.003⟩
- DOI
- DOI : 10.1016/j.jctb.2021.10.003
- Accès au bibtex
-
- auteur
- Jørgen Bang-Jensen, Stéphane Bessy, Daniel Gonçalves, Lucas Picasarri-Arrieta
- titre
- Complexity of some arc-partition problems for digraphs
- article
- Theoretical Computer Science, 2022, 928, pp.167-182. ⟨10.1016/j.tcs.2022.06.023⟩
- DOI
- DOI : 10.1016/j.tcs.2022.06.023
- Accès au texte intégral et bibtex
-
- auteur
- Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo
- titre
- Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
- article
- Journal of Graph Theory, 2022, 100 (2), pp.294-314. ⟨10.1002/jgt.22779⟩
- DOI
- DOI : 10.1002/jgt.22779
- Accès au texte intégral et bibtex
-
- auteur
- Jørgen Bang-Jensen, Frédéric Havet, Matthias Kriesell, A. Yeo
- titre
- Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
- article
- Journal of Graph Theory, 2022, 99 (4), pp.615-636. ⟨10.1002/jgt.22755⟩
- DOI
- DOI : 10.1002/jgt.22755
- Accès au bibtex
-
- auteur
- Jørgen Bang-Jensen, Stéphane Bessy, Anders Yeo
- titre
- Non-separating Spanning Trees and Out-Branchings in Digraphs of Independence Number 2
- article
- Graphs and Combinatorics, 2022, 38 (6), ⟨10.1007/s00373-022-02589-6⟩
- DOI
- DOI : 10.1007/s00373-022-02589-6
- Accès au texte intégral et bibtex
-
- auteur
- Julien Bensmail, Fionn Mc Inerney, Nicolas Nisse
- titre
- Metric Dimension: from Graphs to Oriented Graphs
- article
- Discrete Applied Mathematics, 2022, 323, pp.28-42. ⟨10.1016/j.dam.2020.09.013⟩
- DOI
- DOI : 10.1016/j.dam.2020.09.013
- Accès au texte intégral et bibtex
-
- auteur
- Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta, Dieter Rautenbach
- titre
- Factorially Many Maximum Matchings Close to the Erdős-Gallai Bound
- article
- The Electronic Journal of Combinatorics, 2022, 29 (2), ⟨10.37236/10610⟩
- DOI
- DOI : 10.37236/10610
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
- titre
- Twin-width II: small classes
- article
- Combinatorial Theory, 2022, ⟨10.5070/C62257876⟩
- DOI
- DOI : 10.5070/C62257876
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
- titre
- Twin-width I: tractable FO model checking
- article
- Journal of the ACM (JACM), 2022, 69 (1), pp.1-46. ⟨10.1145/3486655⟩
- DOI
- DOI : 10.1145/3486655
- Accès au texte intégral et bibtex
-
- auteur
- Edouard Bonnet
- titre
- 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^{4/3}
- article
- ACM Transactions on Algorithms, 2022, 18 (2), ⟨10.1145/3494540⟩
- DOI
- DOI : 10.1145/3494540
- Accès au texte intégral et bibtex
-
- auteur
- Carl Feghali
- titre
- Kempe equivalence of 4‐critical planar graphs
- article
- Journal of Graph Theory, 2022, 103 (1), pp.139-147. ⟨10.1002/jgt.22908⟩
- DOI
- DOI : 10.1002/jgt.22908
- Accès au bibtex
-
- auteur
- Emeric Gioan
- titre
- On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids
- article
- Discrete Mathematics, 2022, 345 (7), pp.#112796. ⟨10.1016/j.disc.2022.112796⟩
- DOI
- DOI : 10.1016/j.disc.2022.112796
- Accès au texte intégral et bibtex
-
- auteur
- Frédéric Giroire, Nicolas Nisse, Thibaud Trolliet, Małgorzata Sulkowska
- titre
- Preferential Attachment Hypergraph with High Modularity
- article
- Network Science, 2022, 10 (4), pp.400-429. ⟨10.1017/nws.2022.35⟩
- DOI
- DOI : 10.1017/nws.2022.35
- Accès au texte intégral et bibtex
-
- auteur
- Kolja Knauer, Xuan Hoang La, Petru Valicov
- titre
- Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
- article
- The Electronic Journal of Combinatorics, 2022, 29 (4), ⟨10.37236/10914⟩
- DOI
- DOI : 10.37236/10914
- Accès au texte intégral et bibtex
-
- auteur
- Pierre Monmarché, Mouad Ramil
- titre
- Overdamped limit at stationarity for non-equilibrium Langevin diffusions
- article
- Electronic Communications in Probability, 2022, 27 (none), ⟨10.1214/22-ecp447⟩
- DOI
- DOI : 10.1214/22-ecp447
- Accès au texte intégral et bibtex
-
Conference papers
- auteur
- Pierre Bergé, Anthony Busson, Carl Feghali, Rémi Watrigant
- titre
- 1-Extendability of Independent Sets
- article
- IWOCA 2022, Jun 2022, Trier, Germany. pp.172-185, ⟨10.1007/978-3-031-06678-8_13⟩
- DOI
- DOI : 10.1007/978-3-031-06678-8_13
- Accès au bibtex
-
- auteur
- Pierre Bergé, Édouard Bonnet, Hugues Déprés
- titre
- Deciding twin-width at most 4 is NP-complete
- article
- 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022), Jul 2022, Paris, France. ⟨10.4230/LIPIcs.ICALP.2022.18⟩
- DOI
- DOI : 10.4230/LIPIcs.ICALP.2022.18
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Toruńczyk
- titre
- Twin-width IV: ordered graphs and matrices
- article
- STOC 2022, Jun 2022, Rome, Italy
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk
- titre
- Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
- article
- 37th Annual ACM/IEEE Symposium on Logic in Computer Science ( LICS 2022 ), Aug 2022, Haifa, Israel. ⟨10.1145/3531130.3533367⟩
- DOI
- DOI : 10.1145/3531130.3533367
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé
- titre
- Twin-width VI: the lens of contraction sequences
- article
- SODA 2022, Jan 2022, Alexandria, United States
- Accès au texte intégral et bibtex
-
- auteur
- Thomas Dissaux, Nicolas Nisse
- titre
- Pathlength of Outerplanar graphs
- article
- LATIN 2022 – 15th Latin American Theoretical Informatics Symposium, Nov 2022, Guanajuato, Mexico. pp.172-187, ⟨10.1007/978-3-031-20624-5_11⟩
- DOI
- DOI : 10.1007/978-3-031-20624-5_11
- Accès au texte intégral et bibtex
-
- auteur
- Emeric Gioan
- titre
- On counting orientations for graph homomorphisms and for dually embedded graphs using the Tutte polynomial of matroid perspectives
- article
- ICGT 2022 – 11th International Colloquium on Graph Theory and Combinatorics, Jul 2022, Montpellier, France
- Accès au texte intégral et bibtex
-
Reports
- auteur
- Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Nicolas Nisse, Karol Suchan
- titre
- Semi-proper orientations of dense graphs
- article
- Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France. 2022
- Accès au texte intégral et bibtex
-
Preprints, Working Papers, …
- auteur
- Valentin Bartier, Nicolas Bousquet, Carl Feghali, Marc Heinrich, Benjamin Moore, Théo Pierron
- titre
- Recolouring planar graphs of girth at least five
- article
- 2022
- Accès au texte intégral et bibtex
-
2021
Journal articles
- auteur
- Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon
- titre
- On the tree-width of even-hole-free graphs
- article
- European Journal of Combinatorics, 2021, 98, pp.103394. ⟨10.1016/j.ejc.2021.103394⟩
- DOI
- DOI : 10.1016/j.ejc.2021.103394
- Accès au texte intégral et bibtex
-
- auteur
- Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon
- titre
- On the tree-width of even-hole-free graphs
- article
- European Journal of Combinatorics, 2021, 98, pp.103394. ⟨10.1016/j.ejc.2021.103394⟩
- DOI
- DOI : 10.1016/j.ejc.2021.103394
- Accès au bibtex
-
- auteur
- Jørgen Bang-Jensen, Stéphane Bessy, Jing Huang, Matthias Kriesell
- titre
- Good orientations of unions of edge‐disjoint spanning trees
- article
- Journal of Graph Theory, 2021, 96 (4), pp.594-618. ⟨10.1002/jgt.22633⟩
- DOI
- DOI : 10.1002/jgt.22633
- Accès au bibtex
-
- auteur
- Julien Bensmail, Bi Li, Binlong Li, Nicolas Nisse
- titre
- On Minimizing the Maximum Color for the 1-2-3 Conjecture
- article
- Discrete Applied Mathematics, 2021, 289, pp.32-51. ⟨10.1016/j.dam.2020.09.020⟩
- DOI
- DOI : 10.1016/j.dam.2020.09.020
- Accès au texte intégral et bibtex
-
- auteur
- Stéphane Bessy, Marin Bougeret, Ramaswamy Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, Meirav Zehavi
- titre
- Packing Arc-Disjoint Cycles in Tournaments
- article
- Algorithmica, 2021, 83 (5), pp.1393-1420. ⟨10.1007/s00453-020-00788-2⟩
- DOI
- DOI : 10.1007/s00453-020-00788-2
- Accès au texte intégral et bibtex
-
- auteur
- Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora, Stéphan Thomassé
- titre
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- article
- Journal of the ACM (JACM), 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
- DOI
- DOI : 10.1145/3433160
- Accès au texte intégral et bibtex
-
- auteur
- Ali Dehghan, Frédéric Havet
- titre
- On the semi-proper orientations of graphs
- article
- Discrete Applied Mathematics, 2021, 296, pp.9-25. ⟨10.1016/j.dam.2020.07.003⟩
- DOI
- DOI : 10.1016/j.dam.2020.07.003
- Accès au texte intégral et bibtex
-
- auteur
- Nemanja Draganić, François Dross, Jacob Fox, António Girão, Frédéric Havet, Dániel Korándi, William Lochet, David Munhá Correia, Alex Scott, Benny Sudakov
- titre
- Powers of paths in tournaments
- article
- Combinatorics, Probability and Computing, 2021, pp.1-5. ⟨10.1017/S0963548321000067⟩
- DOI
- DOI : 10.1017/S0963548321000067
- Accès au texte intégral et bibtex
-
- auteur
- François Dross, Frédéric Havet
- titre
- On the unavoidability of oriented trees
- article
- Journal of Combinatorial Theory, Series B, 2021, 151, pp.83-110. ⟨10.1016/j.jctb.2021.06.003⟩
- DOI
- DOI : 10.1016/j.jctb.2021.06.003
- Accès au texte intégral et bibtex
-
- auteur
- Marko Radovanović, Nicolas Trotignon, Kristina Vušković
- titre
- The (theta, wheel)-free graphs Part IV: Induced paths and cycles
- article
- Journal of Combinatorial Theory, Series B, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩
- DOI
- DOI : 10.1016/j.jctb.2020.06.002
- Accès au texte intégral et bibtex
-
- auteur
- Ni Luh Dewi Sintiari, Nicolas Trotignon
- titre
- (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
- article
- Journal of Graph Theory, 2021, ⟨10.1002/jgt.22666⟩
- DOI
- DOI : 10.1002/jgt.22666
- Accès au texte intégral et bibtex
-
- auteur
- Ni Luh Dewi Sintiari, Marcin Pilipczuk, Stéphan Thomassé, Nicolas Trotignon
- titre
- (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
- article
- Journal of Graph Theory, 2021, 97 (4), pp.624-641. ⟨10.1002/jgt.22675⟩
- DOI
- DOI : 10.1002/jgt.22675
- Accès au texte intégral et bibtex
-
Conference papers
- auteur
- Ali Al Zoobi, David Coudert, Nicolas Nisse
- titre
- De la difficulté de trouver des chemins dissimilaires
- article
- ALGOTEL 2021 – 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2021, La Rochelle, France
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant
- titre
- Twin-width and polynomial kernels
- article
- IPEC 2021, Sep 2021, Lisbon, Portugal
- Accès au texte intégral et bibtex
-
- auteur
- Edouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
- titre
- Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
- article
- 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Jul 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.35⟩
- DOI
- DOI : 10.4230/LIPIcs.ICALP.2021.35
- Accès au texte intégral et bibtex
-
- auteur
- Edouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
- titre
- Twin-width II: small classes
- article
- ACM-SIAM Symposium on Discrete Algorithms (SODA21), Jan 2021, Alexandria, United States
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet
- titre
- 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3
- article
- ICALP 2021, Jul 2021, Glasgow, United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.24⟩
- DOI
- DOI : 10.4230/LIPIcs.ICALP.2021.24
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet
- titre
- Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
- article
- STACS 2021, Mar 2021, Saarbrücken, Germany. ⟨10.4230/LIPIcs.STACS.2021.47⟩
- DOI
- DOI : 10.4230/LIPIcs.STACS.2021.47
- Accès au texte intégral et bibtex
-
- auteur
- Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
- titre
- Treelength of Series-parallel graphs
- article
- LAGOS 2021 – XI Latin and American Algorithms, Graphs and Optimization Symposium, May 2021, São Paulo / Virtual, Brazil. ⟨10.1016/j.procs.2021.11.008⟩
- DOI
- DOI : 10.1016/j.procs.2021.11.008
- Accès au texte intégral et bibtex
-
Book sections
- auteur
- Pierre Aboulker, Frédéric Havet, Kolja Knauer, Clément Rambaud
- titre
- On the dichromatic number of surfaces
- article
- Extended Abstracts EuroComb 2021, 14, Springer International Publishing, pp.181-187, 2021, Trends in Mathematics, ⟨10.1007/978-3-030-83823-2_29⟩
- DOI
- DOI : 10.1007/978-3-030-83823-2_29
- Accès au texte intégral et bibtex
-
Reports
- auteur
- Pierre Aboulker, Frédéric Havet, Kolja Knauer, Clément Rambaud
- titre
- On the dichromatic number of surfaces
- article
- [Research Report] Inria; CNRS; I3S; Université Côte D’Azur. 2021
- Accès au bibtex
-
- auteur
- Ali Al Zoobi, David Coudert, Nicolas Nisse
- titre
- On the complexity of finding $k$ shortest dissimilar paths in a graph
- article
- [Research Report] Inria; CNRS; I3S; Université Côte d’Azur. 2021, pp.9
- Accès au texte intégral et bibtex
-
- auteur
- David Coudert, Ali Al Zoobi, Arthur Finkelstein
- titre
- On finding $k$ earliest arrival time journeys in public transit networks
- article
- [Research Report] Inria. 2021
- Accès au texte intégral et bibtex
-
- auteur
- Frédéric Havet, Jørgen Bang-Jensen, Anders Yeo
- titre
- Spanning eulerian subdigraphs in semicomplete digraphs
- article
- [Research Report] Inria; CNRS; I3S; Université côte d’azur. 2021
- Accès au texte intégral et bibtex
-
Software
- auteur
- Ali Al Zoobi, David Coudert, Nicolas Nisse
- titre
- k shortest simple paths
- article
- 2021, ⟨swh:1:dir:4dc5b3b01ddcd9091dd5a628916638a1cefd8e0c;origin=https://gitlab.inria.fr/dcoudert/k-shortest-simple-paths/;visit=swh:1:snp:f0cc7e5f3ec6200d39061db55146a7ab340fee95;anchor=swh:1:rev:124c172d617e485a6b3cd5dc6db7768d86a3a5af⟩
- Accès au bibtex
-
Preprints, Working Papers, …
- auteur
- Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković
- titre
- Maximum independent sets in (pyramid, even hole)-free graphs
- article
- 2021
- Accès au texte intégral et bibtex
-
- auteur
- Louis Esperet, Nicolas Trotignon
- titre
- Coloring graphs with no induced subdivision of $K_4^+$
- article
- 2021
- Accès au texte intégral et bibtex
-
2020
Journal articles
- auteur
- Noga Alon, Jørgen Bang‐jensen, Stéphane Bessy
- titre
- Out‐colourings of digraphs
- article
- Journal of Graph Theory, 2020, 93 (1), pp.88-112. ⟨10.1002/jgt.22476⟩
- DOI
- DOI : 10.1002/jgt.22476
- Accès au bibtex
-
- auteur
- Julien Bensmail, François Dross, Nicolas Nisse
- titre
- Decomposing degenerate graphs into locally irregular subgraphs
- article
- Graphs and Combinatorics, 2020, 36 (6), pp.1869-1889. ⟨10.1007/s00373-020-02193-6⟩
- DOI
- DOI : 10.1007/s00373-020-02193-6
- Accès au texte intégral et bibtex
-
- auteur
- Myriam Preissmann, Cléophée Robin, Nicolas Trotignon
- titre
- On the complexity of colouring antiprismatic graphs
- article
- Algorithmica, 2020, 83 (2), pp.589-612. ⟨10.1007/s00453-020-00767-7⟩
- DOI
- DOI : 10.1007/s00453-020-00767-7
- Accès au bibtex
-
- auteur
- Marko Radovanović, Nicolas Trotignon, Kristina Vušković
- titre
- The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring
- article
- Journal of Combinatorial Theory, Series B, 2020, 143, pp.185-218. ⟨10.1016/j.jctb.2019.07.003⟩
- DOI
- DOI : 10.1016/j.jctb.2019.07.003
- Accès au texte intégral et bibtex
-
Conference papers
- auteur
- Ali Al Zoobi, David Coudert, Nicolas Nisse
- titre
- Compromis espace-temps pour le problème de k plus courts chemins simples
- article
- ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2020, Lyon, France. pp.4
- Accès au texte intégral et bibtex
-
- auteur
- Ali Al Zoobi, David Coudert, Nicolas Nisse
- titre
- Space and Time Trade-Off for the k Shortest Simple Paths Problem
- article
- SEA 2020 – 18th International Symposium on Experimental Algorithms, Jun 2020, Catania, Italy. pp.13, ⟨10.4230/LIPIcs.SEA.2020.18⟩
- DOI
- DOI : 10.4230/LIPIcs.SEA.2020.18
- Accès au texte intégral et bibtex
-
- auteur
- Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, Frédéric Havet
- titre
- Inversion number of an oriented graph and related parameters
- article
- ALGOS 2020 – 1st International Conference on Algebras, Graphs and Ordered Sets, Aug 2020, Nancy / Virtual, France
- Accès au texte intégral et bibtex
-
- auteur
- Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-Joung Kwon
- titre
- Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
- article
- IPEC 2020, Dec 2020, Hong Kong, China
- Accès au texte intégral et bibtex
-
- auteur
- Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
- titre
- Maximum Clique in Disk-Like Intersection Graphs
- article
- FSTTCS 2020, Dec 2020, Goa, India
- Accès au texte intégral et bibtex
-
- auteur
- Edouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
- titre
- Twin-width I: tractable FO model checking
- article
- FOCS 2020, Nov 2020, online, United States
- Accès au texte intégral et bibtex
-
- auteur
- Thibaud Trolliet, Nathann Cohen, Frédéric Giroire, Luc Hogie, Stéphane Pérennes
- titre
- Interest Clustering Coefficient: a New Metric for Directed Networks like Twitter
- article
- COMPLEX NETWORKS 2020 – 9th International Conference on Complex Networks and their Applications, Dec 2020, Madrid / Virtual, Spain
- Accès au texte intégral et bibtex
-
Reports
- auteur
- Ali Al Zoobi, David Coudert, Nicolas Nisse
- titre
- Space and time trade-off for the k shortest simple paths problem
- article
- [Research Report] Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France. 2020
- Accès au texte intégral et bibtex
-
- auteur
- Julio Araujo, Julien Bensmail, Victor Campos, Frédéric Havet, Ana Karolinna Maia de Oliviera, Nicolas Nisse, Ana Silva
- titre
- On finding the best and worst orientations for the metric dimension
- article
- [Research Report] Inria. 2020
- Accès au texte intégral et bibtex
-
- auteur
- Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
- titre
- Treelength of Series-parallel graphs
- article
- [Research Report] Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France. 2020
- Accès au texte intégral et bibtex
-
