Nicolas Trotignon

According to our database1, Nicolas Trotignon authored at least 62 papers between 2004 and 2020.

Collaborative distances:
  • Dijkstra number2 of five.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:



The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring.
J. Comb. Theory, Ser. B, 2020

The (theta, wheel)-free graphs Part II: Structure theorem.
J. Comb. Theory, Ser. B, 2020

The (theta, wheel)-free graphs Part I: Only-prism and only-pyramid graphs.
J. Comb. Theory, Ser. B, 2020

On the tree-width of even-hole-free graphs.
CoRR, 2020

A class of graphs of large rankwidth.
CoRR, 2020

(Theta, triangle)-free and (even hole, K<sub>4</sub>)-free graphs. Part 2 : bounds on treewidth.
CoRR, 2020

Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable.
J. Graph Theory, 2019

Coloring square-free Berge graphs.
J. Comb. Theory, Ser. B, 2019

Maximum independent sets in (pyramid, even hole)-free graphs.
CoRR, 2019

On the complexity of colouring antiprismatic graphs.
CoRR, 2019

(Theta, triangle)-free and (even hole, K<sub>4</sub>)-free graphs. Part 1 : Layered wheels.
CoRR, 2019

The Independent Set Problem Is FPT for Even-Hole-Free Graphs.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

χ-bounds, operations, and chords.
J. Graph Theory, 2018

Connected greedy colouring in claw-free graphs.
CoRR, 2018

Stable Sets in {ISK4, wheel}-Free Graphs.
Algorithmica, 2018

On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph.
J. Graph Theory, 2017

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs.
J. Graph Theory, 2017

Coloring Graphs with Constraints on Connectivity.
J. Graph Theory, 2017

On rank-width of even-hole-free graphs.
Discret. Math. Theor. Comput. Sci., 2017

Preface: Algorithmic Graph Theory on the Adriatic Coast.
Discret. Appl. Math., 2017

A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs.
Algorithmica, 2017

LexBFS, Structure, and Algorithms.
Encyclopedia of Algorithms, 2016

Isolating Highly Connected Induced Subgraphs.
SIAM J. Discret. Math., 2016

Perfect graphs of arbitrarily large clique-chromatic number.
J. Comb. Theory, Ser. B, 2016

Coloring perfect graphs with no balanced skew-partitions.
J. Comb. Theory, Ser. B, 2015

Using SPQR-trees to speed up algorithms based on 2-cutset decompositions.
Electron. Notes Discret. Math., 2015

Wheel-free planar graphs.
Eur. J. Comb., 2015

Vertex elimination orderings for hereditary graph classes.
Discret. Math., 2015

Colouring graphs with constraints on connectivity.
CoRR, 2015

Linear Balanceable and Subcubic Balanceable Graphs.
J. Graph Theory, 2014

Complexity of colouring problems restricted to unichord-free and { square, unichord }-free graphs.
Discret. Appl. Math., 2014

Detecting an induced net subdivision.
J. Comb. Theory, Ser. B, 2013

Substitution and χ-boundedness.
J. Comb. Theory, Ser. B, 2013

Edge-colouring and total-colouring chordless graphs.
Discret. Math., 2013

Perfect graphs: a survey
CoRR, 2013

Parameterized algorithm for weighted independent set problem in bull-free graphs.
CoRR, 2013

Algorithms for square-$3PC(\cdot, \cdot)$-free Berge graphs.
CoRR, 2013

Detecting wheels.
CoRR, 2013

Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It.
SIAM J. Discret. Math., 2012

Excluding Induced Subdivisions of the Bull and Related Graphs.
J. Graph Theory, 2012

Detecting 2-joins faster.
J. Discrete Algorithms, 2012

Combinatorial optimization with 2-joins.
J. Comb. Theory, Ser. B, 2012

On graphs with no induced subdivision of K<sub>4</sub>.
J. Comb. Theory, Ser. B, 2012

The chromatic gap and its extremes.
J. Comb. Theory, Ser. B, 2012

LexBFS, structure and algorithms
CoRR, 2012

Finding an induced subdivision of a digraph.
Electron. Notes Discret. Math., 2011

On Roussel-Rubio-type lemmas and their consequences.
Discret. Math., 2011

Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem.
Contributions Discret. Math., 2011

A structure theorem for graphs with no cycle with a unique chord and its consequences.
J. Graph Theory, 2010

The k-in-a-tree problem for graphs of girth at least k.
Discret. Appl. Math., 2010

Chromatic Index of Chordless Graphs.
Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2010

Coloring Artemis graphs.
Theor. Comput. Sci., 2009

The Four-in-a-Tree Problem in Triangle-Free Graphs.
Graphs Comb., 2009

Algorithms for Square-3PC(., .)-Free Berge Graphs.
SIAM J. Discret. Math., 2008

Decomposing Berge graphs and detecting balanced skew partitions.
J. Comb. Theory, Ser. B, 2008

Detecting induced subgraphs.
Electron. Notes Discret. Math., 2007

A class of perfectly contractile graphs.
J. Comb. Theory, Ser. B, 2006

Algorithms for Perfectly Contractile Graphs.
SIAM J. Discret. Math., 2005

On the structure of self-complementary graphs.
Electron. Notes Discret. Math., 2005

Algorithms for 3PC(., .)-free Berge graphs.
Electron. Notes Discret. Math., 2005

Graphes parfaits : structure et algorithmes. (Perfect graphs : structure and algorithms).
PhD thesis, 2004

Ramsey-type results on singletons, co-singletons and monotone sequences in large collections of sets.
Eur. J. Comb., 2004