Publications HAL de Nicolas BOUSQUET du labo/EPI "LIRMM";"G-SCOP";"LIRIS"

2024

Journal articles

titre
Digraph redicolouring
auteur
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Amadeus Reinald
article
European Journal of Combinatorics, 2024, 116, pp.103876. ⟨10.1016/j.ejc.2023.103876⟩
Accès au texte intégral et bibtex
https://hal.science/hal-04306893/file/Dicolouring_reconfiguration_article-5.pdf BibTex
titre
The smallest 5-chromatic tournament
auteur
Thomas Bellitto, Nicolas Bousquet, Adam Kabela, Théo Pierron
article
Mathematics of Computation, In press, 93 (345), pp.443-458. ⟨10.1090/mcom/3887⟩
Accès au bibtex
https://arxiv.org/pdf/2210.09936 BibTex

Preprints, Working Papers, ...

titre
Fast winning strategies for the attacker in eternal domination
auteur
Guillaume Bagan, Nicolas Bousquet, Nacim Oijid, Théo Pierron
article
2024
Accès au texte intégral et bibtex
https://hal.science/hal-04501118/file/2401.10584.pdf BibTex
titre
Local certification of forbidden subgraphs
auteur
Nicolas Bousquet, Linda Cook, Laurent Feuilloley, Théo Pierron, Sébastien Zeitoun
article
2024
Accès au texte intégral et bibtex
https://hal.science/hal-04467821/file/2402.12148.pdf BibTex
titre
Global certification via perfect hashing
auteur
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
article
2024
Accès au texte intégral et bibtex
https://hal.science/hal-04467834/file/2402.03849.pdf BibTex
titre
Local certification of local properties: tight bounds, trade-offs and new parameters
auteur
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
article
2024
Accès au texte intégral et bibtex
https://hal.science/hal-04440851/file/2312.13702.pdf BibTex

2023

Journal articles

titre
Feedback vertex set reconfiguration in planar graphs
auteur
Nicolas Bousquet, Felix Hommelsheim, Yusuke Kobayashi, Moritz Mühlenthaler, Akira Suzuki
article
Theoretical Computer Science, 2023, 979, pp.114188. ⟨10.1016/J.TCS.2023.114188⟩
Accès au bibtex
BibTex
titre
Galactic token sliding
auteur
Valentin Bartier, Nicolas Bousquet, Amer Mouawad
article
Journal of Computer and System Sciences, 2023, 136 (4), pp.220-248. ⟨10.1016/J.JCSS.2023.03.008⟩
Accès au bibtex
https://arxiv.org/pdf/2204.05549 BibTex
titre
Extremal Independent Set Reconfiguration
auteur
Nicolas Bousquet, Bastien Durain, Théo Pierron, Stéphan Thomassé
article
The Electronic Journal of Combinatorics, 2023, 30 (3), ⟨10.37236/11771⟩
Accès au bibtex
https://arxiv.org/pdf/2301.02020 BibTex
titre
Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
auteur
Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, Chun-Hung Liu, François Pirot, Alex Scott
article
Journal of the European Mathematical Society, 2023, ⟨10.4171/JEMS/1341⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03042934/file/2012.02435.pdf BibTex
titre
Reconfiguration of Spanning Trees with Degree Constraints or Diameter Constraints
auteur
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa
article
Algorithmica, 2023, 85 (9), pp.2779-2816. ⟨10.1007/S00453-023-01117-Z⟩
Accès au bibtex
https://arxiv.org/pdf/2201.04354 BibTex
titre
Locating-dominating sets: from graphs to oriented graphs
auteur
Nicolas Bousquet, Quentin Deschamps, Tuomo Lehtilä, Aline Parreau
article
Discrete Mathematics, 2023, 346 (1), pp.113124. ⟨10.1016/j.disc.2022.113124⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03468604/file/2112.01910.pdf BibTex
titre
A Note on the Flip Distance between Non-crossing Spanning Trees
auteur
Nicolas Bousquet, Valentin Gledel, Jonathan Narboni, Théo Pierron
article
Computing in Geometry and Topology, 2023, ⟨10.57717/cgt.v2i1.36⟩
Accès au bibtex
https://arxiv.org/pdf/2303.07710 BibTex

Reports

titre
Digraph redicolouring
auteur
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Amadeus Reinald
article
Inria. 2023
Accès au texte intégral et bibtex
https://hal.science/hal-04281467/file/2301.03417.pdf BibTex

Preprints, Working Papers, ...

titre
Metric dimension parameterized by treewidth in chordal graphs
auteur
Nicolas Bousquet, Quentin Deschamps, Aline Parreau
article
2023
Accès au texte intégral et bibtex
https://hal.science/hal-04154690/file/2_trees%20%281%29.pdf BibTex

2022

Journal articles

titre
Improved square coloring of planar graphs
auteur
Nicolas Bousquet, Quentin Deschamps, Lucas de Meyer, Théo Pierron
article
Discrete Mathematics, 2022, 346 (4), pp.113288. ⟨10.1016/j.disc.2022.113288⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03897415/file/2112.12512.pdf BibTex
titre
(Sub)linear kernels for edge modification problems toward structured graph classes
auteur
Gabriel Bathie, Nicolas Bousquet, Yixin Cao, Yuping Ke, Théo Pierron
article
Algorithmica, 2022, 84 (11), pp.3338-3364. ⟨10.1007/s00453-022-00969-1⟩
Accès au texte intégral et bibtex
https://hal.science/hal-04084691/file/sublinear_kernels-1.pdf BibTex
titre
Chordal Directed Graphs Are Not $\chi$-Bounded
auteur
Pierre Aboulker, Nicolas Bousquet, Rémi de Verclos
article
The Electronic Journal of Combinatorics, 2022, 29 (2), ⟨10.37236/11050⟩
Accès au bibtex
https://arxiv.org/pdf/2202.01006 BibTex
titre
A polynomial version of Cereceda's conjecture
auteur
Nicolas Bousquet, Marc Heinrich
article
Journal of Combinatorial Theory, Series B, 2022, 155, pp.1-16. ⟨10.1016/j.jctb.2022.01.006⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02167051/file/1903.05619.pdf BibTex
titre
Degeneracy of P_t-free and C_{\>= t}-free graphs with no large complete bipartite subgraphs
auteur
Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
article
Journal of Combinatorial Theory, Series B, 2022, 152, pp.353-378. ⟨10.1016/j.jctb.2021.10.005⟩
Accès au bibtex
https://arxiv.org/pdf/2012.03686 BibTex

Conference papers

titre
Galactic Token Sliding
auteur
Valentin Bartier, Nicolas Bousquet, Amer Mouawad
article
European Symposium on Algorithms, Sep 2022, Potsdam, Germany. ⟨10.4230/LIPIcs.ESA.2022.15⟩
Accès au bibtex
https://arxiv.org/pdf/2204.05549 BibTex
titre
What Can Be Certified Compactly?
auteur
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
article
PODC '22: ACM Symposium on Principles of Distributed Computing, Jul 2022, Salerno, Italy. pp.131-140, ⟨10.1145/3519270.3538416⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03773011/file/2202.06065.pdf BibTex
titre
Token Sliding on Graphs of Girth Five.
auteur
Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer Mouawad, Sebastian Siebertz
article
WG, Jun 2022, Tubingen, Germany. pp.56--69, ⟨10.1007/978-3-031-15914-5\_5⟩
Accès au bibtex
https://arxiv.org/pdf/2205.01009 BibTex
titre
Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint
auteur
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa
article
STACS, Mar 2022, Marseille, France. pp.15:1--15:21, ⟨10.4230/LIPIcs.STACS.2022.15⟩
Accès au bibtex
BibTex
titre
PACE Challenge 2021: heuristique pour le cluster editing problem
auteur
Valentin Bartier, Bathie Gabriel, Nicolas Bousquet, Marc Heinrich, Théo Pierron, Ulysse Prieto
article
23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Villeurbanne - Lyon, France
Accès au bibtex
BibTex

Preprints, Working Papers, ...

titre
Recolouring planar graphs of girth at least five
auteur
Valentin Bartier, Nicolas Bousquet, Carl Feghali, Marc Heinrich, Benjamin Moore, Théo Pierron
article
2022
Accès au texte intégral et bibtex
https://hal.science/hal-03773048/file/Recoloring_Planar_graphs_of_large_girth.pdf BibTex
titre
Short and local transformations between ($\Delta+1$)-colorings
auteur
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, Mikaël Rabie
article
2022
Accès au texte intégral et bibtex
https://hal.science/hal-03663638/file/main.pdf BibTex

2021

Journal articles

titre
Recoloring graphs of treewidth 2
auteur
Nicolas Bousquet, Valentin Bartier, Marc Heinrich
article
Discrete Mathematics, 2021, 344 (12), pp.112553. ⟨10.1016/j.disc.2021.112553⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03394367/file/S0012365X21002661.pdf BibTex
titre
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping
auteur
Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, Amer Mouawad
article
Algorithmica, 2021, 83 (9), pp.2914-2951. ⟨10.1007/s00453-021-00848-1⟩
Accès au bibtex
https://arxiv.org/pdf/2007.01673 BibTex
titre
Packing and Covering Balls in Graphs Excluding a Minor
auteur
Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, William Lochet, Carole Muller, François Pirot
article
Combinatorica, 2021, 41 (3), pp.299-318. ⟨10.1007/s00493-020-4423-3⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03281264/file/2001.04517.pdf BibTex
titre
Frozen (Δ + 1)-colourings of bounded degree graphs
auteur
Marthe Bonamy, Nicolas Bousquet, Guillem Perarnau
article
Combinatorics, Probability and Computing, 2021, 30 (3), pp.330-343. ⟨10.1017/S0963548320000139⟩
Accès au bibtex
https://arxiv.org/pdf/1811.12650 BibTex
titre
Graph Isomorphism for $$(H_1,H_2)$$-Free Graphs: An Almost Complete Dichotomy
auteur
Nicolas Bousquet, Marthe Bonamy, Konrad Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron
article
Algorithmica, 2021, 83 (3), pp.822-852. ⟨10.1007/s00453-020-00747-x⟩
Accès au bibtex
https://arxiv.org/pdf/1811.12252 BibTex
titre
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
auteur
Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora, Stéphan Thomassé
article
Journal of the ACM (JACM), 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03107441/file/arxiv.pdf BibTex

Conference papers

titre
Local Certification of Graph Decompositions and Applications to Minor-Free Classes
auteur
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
article
25th International Conference on Principles of Distributed Systems, OPODIS 2021, Dec 2021, Strasbourg, France. ⟨10.4230/LIPIcs.OPODIS.2021.22⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03610456/file/LIPIcs-OPODIS-2021-22.pdf BibTex
titre
Local certification of graph decompositions and applications to minor-free classes
auteur
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
article
25th International Conference on Principles of Distributed Systems, OPODIS 2021, Dec 2021, Starsbourg, France. pp.22:1--22:17, ⟨10.4230/LIPIcs.OPODIS.2021.22⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03772974/file/CerTIfication_H_minor_free.pdf BibTex
titre
Distributed Recoloring of Interval and Chordal Graphs
auteur
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, Mikaël Rabie
article
25th International Conference on Principles of Distributed Systems, OPODIS 2021, Dec 2021, Strasbourg, France. ⟨10.4230/LIPIcs.OPODIS.2021.19⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03610449/file/LIPIcs-OPODIS-2021-19.pdf BibTex
titre
PACE Solver Description: µSolver - Heuristic Track *
auteur
Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, Ulysse Prieto
article
16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Nov 2021, Lisbon, Portugal. ⟨10.4230/LIPIcs.IPEC.2021.33⟩
Accès au texte intégral et bibtex
https://hal.science/hal-04084587/file/LIPIcs-IPEC-2021-33.pdf BibTex
titre
Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes
auteur
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
article
35th International Symposium on Distributed Computing, (DISC)2021,, Oct 2021, Freiburg, Germany. ⟨10.4230/LIPIcs.DISC.2021.49⟩
Accès au bibtex
https://arxiv.org/pdf/2108.00059 BibTex
titre
TS-Reconfiguration of Dominating Sets in Circle and Circular-Arc Graphs
auteur
Nicolas Bousquet, Alice Joffard
article
FCT 2021, Sep 2021, Athenes, Greece. ⟨10.1007/978-3-030-86593-1_8⟩
Accès au bibtex
https://arxiv.org/pdf/2102.10568 BibTex
titre
PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters
auteur
Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, Ulysse Prieto
article
16th International Symposium on Parameterized and Exact Computation, IPEC 2021, Sep 2021, Lisbonne, Portugal. pp.29:1-29:4, ⟨10.4230/LIPIcs.IPEC.2021.29⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03671173/file/Summary_PACE_exact_track.pdf BibTex
titre
(Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes
auteur
Gabriel Bathie, Nicolas Bousquet, Yixin Cao, Yuping Ke, Théo Pierron
article
16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Sep 2021, Lisboa, Portugal. ⟨10.4230/LIPIcs.IPEC.2021.8⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03773065/file/sublinear_kernels.pdf BibTex
titre
Distributed algorithms for fractional coloring
auteur
Nicolas Bousquet, Louis Esperet, François Pirot
article
28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021), Jun 2021, Wroclaw, Poland. pp.15-30, ⟨10.1007/978-3-030-79527-6_2⟩
Accès au bibtex
https://arxiv.org/pdf/2012.01752 BibTex

Book sections

titre
On the Cycle Rank Conjecture About Metric Dimension and Zero Forcing Number in Graphs
auteur
Nicolas Bousquet, Quentin Deschamps, Ignacio Pelayo, Aline Parreau
article
Extended Abstracts EuroComb 2021, 14, Springer International Publishing, pp.515-520, 2021, Trends in Mathematics, ⟨10.1007/978-3-030-83823-2_83⟩
Accès au bibtex
BibTex

Proceedings

titre
Reconfiguration of Spanning Trees with Many or Few Leaves
auteur
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa
article
European Symposium on Algorithms (ESA), 2021, ⟨10.4230/LIPIcs.ESA.2020.24⟩
Accès au bibtex
https://arxiv.org/pdf/2006.14309 BibTex

Preprints, Working Papers, ...

titre
Metric dimension on sparse graphs and its applications to zero forcing sets
auteur
Nicolas Bousquet, Quentin Deschamps, Aline Parreau, Ignacio M Pelayo
article
2021
Accès au texte intégral et bibtex
https://hal.science/hal-03421594/file/Metric%20dimension%20on%20sparse%20graphs.pdf BibTex

2020

Journal articles

titre
A note on the simultaneous edge coloring
auteur
Nicolas Bousquet, Bastien Durain
article
Discrete Mathematics, 2020, 343 (5), pp.111781. ⟨10.1016/j.disc.2019.111781⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02935482/file/S0012365X19304637.pdf BibTex
titre
Parameterized Complexity of Independent Set in H-free Graphs
auteur
Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant
article
Algorithmica, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Accès au texte intégral et bibtex
https://hal.science/hal-03015353/file/main.pdf BibTex

Book sections

titre
Approximating Shortest Connected Graph Transformation for Trees
auteur
Nicolas Bousquet, Alice Joffard
article
SOFSEM 2020: SOFSEM 2020: Theory and Practice of Computer Science, pp.76-87, 2020, ⟨10.1007/978-3-030-38919-2_7⟩
Accès au bibtex
BibTex

Preprints, Working Papers, ...

titre
Surfaces have (asymptotic) dimension 2
auteur
Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, François Pirot, Alex Scott
article
2020
Accès au bibtex
https://arxiv.org/pdf/2007.03582 BibTex

2019

Journal articles

titre
A proof of the Erdős–Sands–Sauer–Woodrow conjecture
auteur
Nicolas Bousquet, William Lochet, Stéphan Thomassé
article
Journal of Combinatorial Theory, Series B, 2019, Elsevier Journal of Combinatorial Theory, Series B, 137, pp.316-319. ⟨10.1016/j.jctb.2018.11.005⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02158330/file/monoPath.pdf BibTex
titre
On a conjecture of Mohar concerning Kempe equivalence of regular graphs
auteur
Marthe Bonamy, Nicolas Bousquet, Carl Feghali, Matthew Johnson
article
Journal of Combinatorial Theory, Series B, 2019, 135, pp.179-199. ⟨10.1016/j.jctb.2018.08.002⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02467364/file/1510.06964.pdf BibTex
titre
Exact distance coloring in trees
auteur
Nicolas Bousquet, Louis Esperet, Ararat Harutyunyan, Rémi de Joannis de Verclos
article
Combinatorics, Probability and Computing, 2019, 28 (2), pp.177-186. ⟨10.1017/S0963548318000378⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01525789/file/exact_distance.pdf BibTex
titre
Distributed coloring in sparse graphs with fewer colors
auteur
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, Louis Esperet
article
The Electronic Journal of Combinatorics, 2019, 26 (4), ⟨10.37236/8395⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02333202/file/1802.05582.pdf BibTex

Conference papers

titre
When Maximum Stable Set Can Be Solved in FPT Time
auteur
Edouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant
article
30th International Symposium on Algorithms and Computation (ISAAC 2019), Dec 2019, Shanghai, China. ⟨10.4230/LIPIcs.ISAAC.2019.49⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02935501/file/LIPIcs-ISAAC-2019-49.pdf BibTex
titre
Linear Transformations between colorings in chordal graphs
auteur
Nicolas Bousquet, Bartier Valentin
article
ESA 2019 - European Symposium on Algorithms, Sep 2019, Munich, Germany. pp.24:1,24:15, ⟨10.4230/LIPIcs.ESA.2019.24⟩
Accès au bibtex
https://arxiv.org/pdf/1907.01863 BibTex
titre
The Perfect Matching Reconfiguration Problem
auteur
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, Kunihiro Wasa
article
MFCS 2019 - 44th International Symposium on Mathematical Foundations of Computer Science, Aug 2019, Aachen, Germany. pp.1-14, ⟨10.4230/LIPIcs.MFCS.2019.80⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-02335588/file/LIPIcs-MFCS-2019-80.pdf BibTex
titre
Shortest Reconfiguration of Matchings
auteur
Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, Moritz Mühlenthaler
article
WG 2019 - 45th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2019, Vall de Núria, Spain. pp.162-174, ⟨10.1007/978-3-030-30786-8_13⟩
Accès au bibtex
https://arxiv.org/pdf/1812.05419 BibTex

Preprints, Working Papers, ...

titre
Approximating Shortest Connected Graph Transformation for Trees
auteur
Nicolas Bousquet, Alice Joffard
article
2019
Accès au texte intégral et bibtex
https://hal.science/hal-02358489/file/Approx_reconfiguration_degree_Arxiv.pdf BibTex

2018

Journal articles

titre
χ-bounded families of oriented graphs
auteur
Pierre Aboulker, Jørgen Bang-Jensen, Nicolas Bousquet, Pierre Charbit, Frédéric Havet, Frédéric Maffray, Jose Zamora
article
Journal of Graph Theory, 2018, 89 (3), pp.304 - 326. ⟨10.1002/jgt.22252⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01882395/file/Induced-digraphs-revised.pdf BibTex
titre
Decomposition techniques applied to the Clique-Stable set separation problem
auteur
Nicolas Bousquet, Aurélie Lagoutte, Frédéric Maffray, Lucas Pastor
article
Discrete Mathematics, 2018, 341 (5), pp.1492 - 1501. ⟨10.1016/j.disc.2017.10.014⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01804017/file/1703.07106.pdf BibTex
titre
Recoloring graphs via tree decompositions
auteur
Nicolas Bousquet, Marthe Bonamy
article
European Journal of Combinatorics, 2018, 69, pp.200 - 213. ⟨10.1016/j.ejc.2017.10.010⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01804109/file/1403.6386.pdf BibTex
titre
Multicut Is FPT
auteur
Nicolas Bousquet, Jean Daligault, Stéphan Thomassé
article
SIAM Journal on Computing, 2018, 47 (1), pp.166-207. ⟨10.1137/140961808⟩
Accès au bibtex
BibTex
titre
Frozen colourings of bounded degree graphs
auteur
Marthe Bonamy, Nicolas Bousquet, Guillem Perarnau
article
Electronic Notes in Discrete Mathematics, 2018, 68, pp.167--172. ⟨10.1016/j.endm.2018.06.029⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02527067/file/DMD_frozen.pdf BibTex

Conference papers

titre
EPTAS for Max Clique on Disks and Unit Balls
auteur
Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé
article
FOCS: Foundations of Computer Science, Oct 2018, Paris, France. ⟨10.1109/FOCS.2018.00060⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01962198/file/eptasDisk.pdf BibTex
titre
Reconfiguration of graphs with connectivity constraints
auteur
Nicolas Bousquet, Arnaud Mary
article
WAOA 2018 - International Workshop on Approximation and Online Algorithms, Aug 2018, Helsinki, Finland. pp.295-309, ⟨10.1007/978-3-030-04693-4_18⟩
Accès au bibtex
https://arxiv.org/pdf/1809.05443 BibTex
titre
Parameterized Complexity of Independent Set in H-free graphs
auteur
Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant
article
IPEC 2018 - 13th International Symposium on Parameterized and Exact Computation, Aug 2018, Helsinki, Finland. ⟨10.4230/LIPIcs.CVIT.2016.23⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01962369/file/proceedings-ipec18.pdf BibTex
titre
Distributed coloring in sparse graphs with fewer colors
auteur
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, Louis Esperet
article
ACM Symposium on Principles of Distributed Computing (PODC 2018), Jul 2018, Egham, United Kingdom. pp.419-425, ⟨10.1145/3212734.3212740⟩
Accès au bibtex
https://arxiv.org/pdf/1802.05582 BibTex

2017

Journal articles

titre
A Vizing-like theorem for union vertex-distinguishing edge coloring
auteur
Nicolas Bousquet, Antoine Dailly, Eric Duchene, Hamamache Kheddouci, Aline Parreau
article
Discrete Applied Mathematics, 2017, 232, pp.88-98. ⟨10.1016/j.dam.2017.07.002⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01313088/file/articleChiURevised.pdf BibTex
titre
Colorful paths for 3-chromatic graphs
auteur
Nicolas Bousquet, Stéphane Bessy
article
Discrete Mathematics, 2017, 340 (5), pp.1000-1007. ⟨10.1016/j.disc.2017.01.016⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01592548/file/1503.00965.pdf BibTex

Conference papers

titre
Token Jumping in minor-closed classes
auteur
Nicolas Bousquet, Arnaud Mary, Aline Parreau
article
International symposium on fundamentals of computer theory (FCT 2017), Sep 2017, Bordeaux, France. pp.136-149, ⟨10.1007/978-3-662-55751-8_12⟩
Accès au bibtex
https://arxiv.org/pdf/1706.09608 BibTex
titre
Token Sliding on Chordal Graphs
auteur
Nicolas Bousquet, Marthe Bonamy
article
WG (Workshop on Graphs), Jun 2017, Heeze, Netherlands
Accès au bibtex
BibTex
titre
Computing maximum cliques in B 2 EPG graphs
auteur
Nicolas Bousquet, Marc Heinrich
article
WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands
Accès au texte intégral et bibtex
https://hal.science/hal-01557335/file/clique-bepg_arxiv.pdf BibTex

Preprints, Working Papers, ...

titre
Reconfiguring Independent Sets in Cographs
auteur
Marthe Bonamy, Nicolas Bousquet
article
2017
Accès au bibtex
https://arxiv.org/pdf/1406.1433 BibTex
titre
The Erdős-Hajnal Conjecture for Long Holes and Anti-holes
auteur
Marthe Bonamy, Nicolas Bousquet, Stéphan Thomassé
article
2017
Accès au bibtex
https://arxiv.org/pdf/1408.1964 BibTex

2016

Journal articles

titre
The Erdös--Hajnal Conjecture for Long Holes and Antiholes
auteur
Marthe Bonamy, Nicolas Bousquet, Stéphan Thomassé
article
SIAM Journal on Discrete Mathematics, 2016, 30 (2), pp.1159-1164. ⟨10.1137/140981745⟩
Accès au bibtex
BibTex

Preprints, Working Papers, ...

titre
χ-bounded families of oriented graphs
auteur
Pierre Aboulker, Jørgen Bang-Jensen, Nicolas Bousquet, Pierre Charbit, Frédéric Havet, Frédéric Maffray, Jose Zamora
article
2016
Accès au texte intégral et bibtex
https://inria.hal.science/hal-01412667/file/chiboundDMay17.pdf BibTex

2015

Journal articles

titre
VC-dimension and Erdős–Pósa property
auteur
Nicolas Bousquet, Stéphan Thomassé
article
Discrete Mathematics, 2015, 338, pp.2302-2317. ⟨10.1016/j.disc.2015.05.026⟩
Accès au bibtex
BibTex
titre
Excluding cycles with a fixed number of chords
auteur
Pierre Aboulker, Nicolas Bousquet
article
Discrete Applied Mathematics, 2015, 180, pp.11-24. ⟨10.1016/j.dam.2014.08.006⟩
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01350552/file/1304.1718.pdf BibTex
titre
The Erdős–Hajnal conjecture for paths and antipaths
auteur
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
article
Journal of Combinatorial Theory, Series B, 2015, 113, pp.261-264. ⟨10.1016/j.jctb.2015.01.001⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01134469/file/pathantipath_elsarticle_revisee.pdf BibTex
titre
Identifying codes in hereditary classes of graphs and VC-dimension
auteur
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, Stéphan Thomassé
article
SIAM Journal on Discrete Mathematics, 2015, 29 (4), pp.2047-2064. ⟨10.1137/14097879X⟩
Accès au texte intégral et bibtex
https://hal.science/hal-01038012/file/Identifying_codes_and_VC-dimension_final_siam.pdf BibTex

2014

Journal articles

titre
Density modification based reliability sensitivity analysis
auteur
Paul Lemaître, Ekaterina Sergienko, Aurélie Arnaud, Nicolas Bousquet, Fabrice Gamboa, Bertrand Iooss
article
Journal of Statistical Computation and Simulation, 2014, 85 (6), pp.1200-1223. ⟨10.1080/00949655.2013.873039⟩
Accès au texte intégral et bibtex
https://hal.science/hal-00737978/file/Article_v72_pour_HAL.pdf BibTex
titre
Brooks’ theorem on powers of graphs
auteur
Marthe Bonamy, Nicolas Bousquet
article
Discrete Mathematics, 2014, 325, pp.12-16. ⟨10.1016/j.disc.2014.01.024⟩
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264422/file/1310.5493.pdf BibTex
titre
Clique versus Independent Set
auteur
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
article
European Journal of Combinatorics, 2014, 40, pp.73-92. ⟨10.1016/j.ejc.2014.02.003⟩
Accès au texte intégral et bibtex
https://inria.hal.science/hal-00958647/file/CS-sep_pour_journal_revisee.pdf BibTex
titre
Parameterized domination in circle graphs
auteur
Christophe Paul, Nicolas Bousquet, Daniel Gonçalves, George Mertzios, Ignasi Sau, Stéphan Thomassé
article
Theory of Computing Systems, 2014, 54 (1), pp.45-72. ⟨10.1007/s00224-013-9478-8⟩
Accès au bibtex
https://arxiv.org/pdf/1205.3728 BibTex

Conference papers

titre
Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
auteur
Marin Bougeret, Nicolas Bousquet, Rodolphe Giroudeau, Rémi Watrigant
article
SOFSEM: Theory and Practice of Computer Science, Jan 2014, Nový Smokovec, Slovakia. pp.150-161, ⟨10.1007/978-3-319-04298-5_14⟩
Accès au bibtex
BibTex

2013

Conference papers

titre
Adjacent vertex-distinguishing edge coloring of graphs
auteur
Marthe Bonamy, Nicolas Bousquet, Hervé Hocquard
article
EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2013, Pise, Italy. pp.313-318, ⟨10.1007/978-88-7642-475-5_50⟩
Accès au bibtex
BibTex
titre
Recoloring bounded treewidth graphs
auteur
Marthe Bonamy, Nicolas Bousquet
article
LAGOS: Latin-American Algorithms, Graphs, and Optimization Symposium, 2013, Playa del Carmen, Mexico. pp.293-297, ⟨10.1016/j.endm.2013.10.040⟩
Accès au bibtex
BibTex

Reports

titre
Parameterized Complexity of the Sparsest k-Subgraph in Chordal Graphs
auteur
Rémi Watrigant, Nicolas Bousquet, Marin Bougeret, Rodolphe Giroudeau
article
[Research Report] RR-13033, LIRMM. 2013
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00875132/file/researchReport.pdf BibTex

2012

Journal articles

titre
Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs
auteur
Stéphan Thomassé, Nicolas Bousquet
article
Combinatorics, Probability and Computing, 2012, 21, pp.512-514. ⟨10.1017/S0963548312000065⟩
Accès au bibtex
https://arxiv.org/pdf/1107.3491 BibTex

Conference papers

titre
Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata
auteur
Christof Loeding, Nicolas Bousquet
article
LATA'10: Language and Automata Theory and Applications, Germany. pp.118-129
Accès au bibtex
BibTex
titre
Parameterized domination in circle graphs
auteur
Nicolas Bousquet, Daniel Gonçalves, George B. Mertzios, Christophe Paul, Ignasi Sau, Stéphan Thomassé
article
WG 2012 - 38th International Workshop on Graph Theoretic-Concepts in Computer Science, Jun 2012, Jerusalem, Israel. pp.45-72, ⟨10.1007/s00224-013-9478-8⟩
Accès au texte intégral et bibtex
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738534/file/1205.3728.pdf BibTex

2011

Conference papers

titre
Multicut is FPT
auteur
Nicolas Bousquet, Jean Daligault, Stéphan Thomassé
article
STOC 2011 - 43rd Symposium on Theory of Computing, Jun 2011, San José, United States. pp.459-468, ⟨10.1145/1993636.1993698⟩
Accès au bibtex
https://arxiv.org/pdf/1010.5197 BibTex

2009

Conference papers

titre
A Polynomial Kernel For Multicut In Trees
auteur
Nicolas Bousquet, Jean Daligault, Stéphan Thomassé, Anders Yeo
article
STACS'2009: 26th International Symposium on Theoretical Aspects of Computer Science, Feb 2009, Freiburg, Germany. pp.183-194
Accès au texte intégral et bibtex
https://inria.hal.science/inria-00359171/file/Bousquet_new.pdf BibTex