Nicolas Trotignon

108 papers A* 1B 3C 2Journal 100
YearRankTypeTitle / Venue / Authors
2026 J jnl
Induced minor models. I. Structural properties and algorithmic consequences.
J. Comput. Syst. Sci.
Nicolas Bousquet, Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanic, Anthony Perez, Nicolas Trotignon
2025 B conf
A Structural Description of Zykov and Blanche Descartes Graphs.
WG
Malory Marin, Stéphan Thomassé, Nicolas Trotignon, Rémi Watrigant
2025 J jnl
Every Graph is Essential to Large Treewidth.
CoRR
Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana, Nicolas Trotignon
2025 J jnl
Graphs without a 3-Connected Subgraph are 4-Colourable.
Electron. J. Comb.
Édouard Bonnet, Carl Feghali, Tung Nguyen, Alex Scott, Paul D. Seymour, Stéphan Thomassé, Nicolas Trotignon
2025 A* conf
Induced Disjoint Paths Without an Induced Minor.
ICALP
Pierre Aboulker, Édouard Bonnet, Timothé Picavet, Nicolas Trotignon
2025 J jnl
Induced Disjoint Paths Without an Induced Minor.
CoRR
Pierre Aboulker, Édouard Bonnet, Timothé Picavet, Nicolas Trotignon
2025 J jnl
On the structure of (4K
CoRR
Chính T. Hoàng, Ramin Javadi, Nicolas Trotignon
2025 J jnl
Pathographs and some (un)decidability results.
CoRR
Daniel Carter, Nicolas Trotignon
2025 J jnl
Unavoidable Induced Subgraphs in Graphs with Complete Bipartite Induced Minors.
SIAM J. Discret. Math.
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen, Nicolas Trotignon, Sebastian Wiederrecht
2024 J jnl
A class of graphs with large rankwidth.
Discret. Math.
Chính T. Hoàng, Nicolas Trotignon
2024 J jnl
A structural description of Zykov and Blanche Descartes graphs.
CoRR
Malory Marin, Stéphan Thomassé, Nicolas Trotignon, Rémi Watrigant
2024 J jnl
Burling graphs revisited, part II: Structure.
Eur. J. Comb.
Pegah Pournajafi, Nicolas Trotignon
2024 J jnl
Burling graphs revisited, part III: Applications to χ-boundedness.
Eur. J. Comb.
Pegah Pournajafi, Nicolas Trotignon
2024 C conf
Detecting K
IWOCA
Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanic, Anthony Perez, Nicolas Trotignon
2024 J jnl
Detecting K
CoRR
Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanic, Anthony Perez, Nicolas Trotignon
2024 J jnl
Graphs with all holes the same length.
J. Comb. Theory B
Linda Cook, Jake Horsfield, Myriam Preissmann, Cléophée Robin, Paul D. Seymour, Ni Luh Dewi Sintiari, Nicolas Trotignon, Kristina Vuskovic
2024 J jnl
Graphs without a 3-connected subgraph are 4-colorable.
CoRR
Édouard Bonnet, Carl Feghali, Stéphan Thomassé, Nicolas Trotignon
2024 J jnl
Unavoidable induced subgraphs in graphs with complete bipartite induced minors.
CoRR
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen, Nicolas Trotignon, Sebastian Wiederrecht
2023 J jnl
Burling graphs revisited, part I: New characterizations.
Eur. J. Comb.
Pegah Pournajafi, Nicolas Trotignon
2022 J jnl
Graphs with polynomially many minimal separators.
J. Comb. Theory B
Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic
2021 J jnl
(Theta, triangle)-free and (even hole, K
J. Graph Theory
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon
2021 J jnl
(Theta, triangle)-free and (even hole, K
J. Graph Theory
Ni Luh Dewi Sintiari, Nicolas Trotignon
2021 J jnl
Burling graphs revisited - Part 1 New characterizations.
CoRR
Pegah Pournajafi, Nicolas Trotignon
2021 J jnl
Burling graphs revisited, part III: Applications to χ-boundedness.
CoRR
Pegah Pournajafi, Nicolas Trotignon
2021 J jnl
On the Complexity of Colouring Antiprismatic Graphs.
Algorithmica
Myriam Preissmann, Cléophée Robin, Nicolas Trotignon
2021 J jnl
On the tree-width of even-hole-free graphs.
Eur. J. Comb.
Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon
2021 J jnl
The (theta, wheel)-free graphs Part IV: Induced paths and cycles.
J. Comb. Theory B
Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
2020 J jnl
(Theta, triangle)-free and (even hole, K
CoRR
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon
2020 J jnl
A class of graphs of large rankwidth.
CoRR
Chính T. Hoàng, Nicolas Trotignon
2020 J jnl
On the tree-width of even-hole-free graphs.
CoRR
Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon
2020 J jnl
The (theta, wheel)-free graphs Part I: Only-prism and only-pyramid graphs.
J. Comb. Theory B
Emilie Diot, Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
2020 J jnl
The (theta, wheel)-free graphs Part II: Structure theorem.
J. Comb. Theory B
Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
2020 J jnl
The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring.
J. Comb. Theory B
Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
2019 J jnl
(Theta, triangle)-free and (even hole, K
CoRR
Ni Luh Dewi Sintiari, Nicolas Trotignon
2019 J jnl
Coloring square-free Berge graphs.
J. Comb. Theory B
Maria Chudnovsky, Irene Lo, Frédéric Maffray, Nicolas Trotignon, Kristina Vuskovic
2019 J jnl
Maximum independent sets in (pyramid, even hole)-free graphs.
CoRR
Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic
2019 J jnl
On the complexity of colouring antiprismatic graphs.
CoRR
Myriam Preissmann, Cléophée Robin, Nicolas Trotignon
2019 B conf
The Independent Set Problem Is FPT for Even-Hole-Free Graphs.
IPEC
Edin Husic, Stéphan Thomassé, Nicolas Trotignon
2019 J jnl
Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable.
J. Graph Theory
Maria Chudnovsky, Chun-Hung Liu, Oliver Schaudt, Sophie Spirkl, Nicolas Trotignon, Kristina Vuskovic
2018 J jnl
Connected greedy colouring in claw-free graphs.
CoRR
Ngoc-Khang Le, Nicolas Trotignon
2018 J jnl
Stable Sets in {ISK4, wheel}-Free Graphs.
Algorithmica
Martin Milanic, Irena Penev, Nicolas Trotignon
2018 J jnl
χ-bounds, operations, and chords.
J. Graph Theory
Nicolas Trotignon, Lan Anh Pham
2017 J jnl
A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs.
Algorithmica
Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic
2017 J jnl
Coloring Graphs with Constraints on Connectivity.
J. Graph Theory
Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon
2017 J jnl
Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs.
J. Graph Theory
Martin Milanic, Nicolas Trotignon
2017 J jnl
On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph.
J. Graph Theory
Nicolas Trotignon, Kristina Vuskovic
2017 J jnl
On rank-width of even-hole-free graphs.
Discret. Math. Theor. Comput. Sci.
Isolde Adler, Ngoc-Khang Le, Haiko Müller, Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
2017 J jnl
Preface: Algorithmic Graph Theory on the Adriatic Coast.
Discret. Appl. Math.
Bostjan Bresar, Pinar Heggernes, Marcin Jakub Kaminski, Martin Milanic, Daniël Paulusma, Primoz Potocnik, Nicolas Trotignon
2016 J jnl
$χ$-bounds, operations and chords.
CoRR
Lan Anh Pham, Nicolas Trotignon
2016 J jnl
Isolating Highly Connected Induced Subgraphs.
SIAM J. Discret. Math.
Irena Penev, Stéphan Thomassé, Nicolas Trotignon
2016 — ch.
LexBFS, Structure, and Algorithms.
Encyclopedia of Algorithms
Nicolas Trotignon
2016 J jnl
On rank-width of even-hole-free graphs.
CoRR
Isolde Adler, Ngoc-Khang Le, Haiko Müller, Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
2016 J jnl
Perfect graphs of arbitrarily large clique-chromatic number.
J. Comb. Theory B
Pierre Charbit, Irena Penev, Stéphan Thomassé, Nicolas Trotignon
2015 J jnl
Coloring perfect graphs with no balanced skew-partitions.
J. Comb. Theory B
Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck, Kristina Vuskovic
2015 J jnl
Colouring graphs with constraints on connectivity.
CoRR
Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon
2015 J jnl
Using SPQR-trees to speed up algorithms based on 2-cutset decompositions.
Electron. Notes Discret. Math.
Celina M. H. de Figueiredo, Hélio B. Macêdo Filho, Zhentao Li, Raphael Carlos Santos Machado, Nicolas Trotignon
2015 J jnl
Vertex elimination orderings for hereditary graph classes.
Discret. Math.
Pierre Aboulker, Pierre Charbit, Nicolas Trotignon, Kristina Vuskovic
2015 J jnl
Wheel-free planar graphs.
Eur. J. Comb.
Pierre Aboulker, Maria Chudnovsky, Paul D. Seymour, Nicolas Trotignon
2014 B conf
A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs.
WG
Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic
2014 J jnl
Complexity of colouring problems restricted to unichord-free and { square, unichord }-free graphs.
Discret. Appl. Math.
Raphael C. S. Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
2014 J jnl
Equistarable graphs and counterexamples to three conjectures on equistable graphs.
CoRR
Martin Milanic, Nicolas Trotignon
2014 J jnl
Linear Balanceable and Subcubic Balanceable Graphs.
J. Graph Theory
Pierre Aboulker, Marko Radovanovic, Nicolas Trotignon, Théophile Trunck, Kristina Vuskovic
2013 J jnl
Algorithms for perfectly contractile graphs.
CoRR
Frédéric Maffray, Nicolas Trotignon
2013 J jnl
Algorithms for square-$3PC(\cdot, \cdot)$-free Berge graphs.
CoRR
Frédéric Maffray, Nicolas Trotignon, Kristina Vuskovic
2013 J jnl
Coloring perfect graphs with no balanced skew-partitions.
CoRR
Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck, Kristina Vuskovic
2013 J jnl
Combinatorial optimization with 2-joins.
CoRR
Nicolas Trotignon, Kristina Vuskovic
2013 J jnl
Complexity of colouring problems restricted to unichord-free and \{square, unichord\}-free graphs.
CoRR
Raphael C. S. Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
2013 J jnl
Detecting an induced net subdivision.
CoRR
Maria Chudnovsky, Paul D. Seymour, Nicolas Trotignon
2013 J jnl
Detecting an induced net subdivision.
J. Comb. Theory B
Maria Chudnovsky, Paul D. Seymour, Nicolas Trotignon
2013 J jnl
Detecting induced subgraphs.
CoRR
Benjamin Lévêque, David Y. Lin, Frédéric Maffray, Nicolas Trotignon
2013 J jnl
Detecting wheels.
CoRR
Emilie Diot, Sébastien Tavenas, Nicolas Trotignon
2013 J jnl
Edge-colouring and total-colouring chordless graphs.
CoRR
Raphael C. S. Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
2013 J jnl
Edge-colouring and total-colouring chordless graphs.
Discret. Math.
Raphael C. S. Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
2013 J jnl
Finding an induced subdivision of a digraph.
CoRR
Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon
2013 J jnl
Graphs that do not contain a cycle with a node that has at least two neighbors on it.
CoRR
Pierre Aboulker, Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
2013 J jnl
Parameterized algorithm for weighted independent set problem in bull-free graphs.
CoRR
Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic
2013 J jnl
Perfect graphs: a survey
CoRR
Nicolas Trotignon
2013 J jnl
Substitution and χ-boundedness.
J. Comb. Theory B
Maria Chudnovsky, Irena Penev, Alex Scott, Nicolas Trotignon
2013 J jnl
The $k$-in-a-tree problem for graphs of girth at least~$k$.
CoRR
Wei Liu, Nicolas Trotignon
2013 J jnl
The four-in-a-tree problem in triangle-free graphs.
CoRR
Nicolas Derhy, Christophe Picouleau, Nicolas Trotignon
2012 J jnl
Combinatorial optimization with 2-joins.
J. Comb. Theory B
Nicolas Trotignon, Kristina Vuskovic
2012 J jnl
Detecting 2-joins faster.
J. Discrete Algorithms
Pierre Charbit, Michel Habib, Nicolas Trotignon, Kristina Vuskovic
2012 J jnl
Excluding Induced Subdivisions of the Bull and Related Graphs.
J. Graph Theory
Maria Chudnovsky, Irena Penev, Alex Scott, Nicolas Trotignon
2012 J jnl
Finding an induced subdivision of a digraph.
Theor. Comput. Sci.
Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon
2012 J jnl
Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It.
SIAM J. Discret. Math.
Pierre Aboulker, Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic
2012 J jnl
LexBFS, structure and algorithms
CoRR
Pierre Aboulker, Pierre Charbit, Maria Chudnovsky, Nicolas Trotignon, Kristina Vuskovic
2012 J jnl
On graphs with no induced subdivision of K
J. Comb. Theory B
Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon
2012 J jnl
The chromatic gap and its extremes.
J. Comb. Theory B
András Gyárfás, András Sebö, Nicolas Trotignon
2011 J jnl
Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem.
Contributions Discret. Math.
Maurice Pouzet, Hamza Si Kaddour, Nicolas Trotignon
2011 J jnl
Detecting 2-joins faster
CoRR
Pierre Charbit, Michel Habib, Nicolas Trotignon, Kristina Vuskovic
2011 J jnl
Finding an induced subdivision of a digraph.
Electron. Notes Discret. Math.
Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon
2011 J jnl
On Roussel-Rubio-type lemmas and their consequences.
Discret. Math.
Nicolas Trotignon, Kristina Vuskovic
2010 J jnl
A structure theorem for graphs with no cycle with a unique chord and its consequences.
J. Graph Theory
Nicolas Trotignon, Kristina Vuskovic
2010 C conf
Chromatic Index of Chordless Graphs.
CTW
Raphael Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
2010 J jnl
The k-in-a-tree problem for graphs of girth at least k.
Discret. Appl. Math.
Wei Liu, Nicolas Trotignon
2009 J jnl
Coloring Artemis graphs.
Theor. Comput. Sci.
Benjamin Lévêque, Frédéric Maffray, Bruce A. Reed, Nicolas Trotignon
2009 J jnl
Detecting induced subgraphs.
Discret. Appl. Math.
Benjamin Lévêque, David Y. Lin, Frédéric Maffray, Nicolas Trotignon
2009 J jnl
The Four-in-a-Tree Problem in Triangle-Free Graphs.
Graphs Comb.
Nicolas Derhy, Christophe Picouleau, Nicolas Trotignon
2008 J jnl
Algorithms for Square-3PC(., .)-Free Berge Graphs.
SIAM J. Discret. Math.
Frédéric Maffray, Nicolas Trotignon, Kristina Vuskovic
2008 J jnl
Decomposing Berge graphs and detecting balanced skew partitions.
J. Comb. Theory B
Nicolas Trotignon
2007 J jnl
Detecting induced subgraphs.
Electron. Notes Discret. Math.
Benjamin Lévêque, David Y. Lin, Frédéric Maffray, Nicolas Trotignon
2006 J jnl
A class of perfectly contractile graphs.
J. Comb. Theory B
Frédéric Maffray, Nicolas Trotignon
2005 J jnl
Algorithms for 3PC(., .)-free Berge graphs.
Electron. Notes Discret. Math.
Frédéric Maffray, Nicolas Trotignon, Kristina Vuskovic
2005 J jnl
Algorithms for Perfectly Contractile Graphs.
SIAM J. Discret. Math.
Frédéric Maffray, Nicolas Trotignon
2005 J jnl
Coloring Artemis graphs
CoRR
Benjamin Lévêque, Frédéric Maffray, Bruce A. Reed, Nicolas Trotignon
2005 J jnl
On the structure of self-complementary graphs.
Electron. Notes Discret. Math.
Nicolas Trotignon
2004 — —
Graphes parfaits : structure et algorithmes. (Perfect graphs : structure and algorithms).
Nicolas Trotignon
2004 J jnl
Ramsey-type results on singletons, co-singletons and monotone sequences in large collections of sets.
Eur. J. Comb.
Sylvain Gravier, Frédéric Maffray, Jérôme Renault, Nicolas Trotignon