56 citations · 715 across the 68 of their papers we have counts for
6 papers · 1 filter
Maximum independent sets in (pyramid, even hole)-free graphs
Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon +1
A \emph{hole} in a graph is an induced cycle with at least 4 vertices. A graph is \emph{even-hole-free} if it does not contain a hole on an even number of vertices. A \emph{pyramid…
The (theta, wheel)-free graphs Part IV: induced paths and cycles
Marko Radovanović, Nicolas Trotignon, Kristina Vušković
A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three internally vertex-disjoint paths of length at least 2 between the same pair of disti…
On the complexity of colouring antiprismatic graphs
Myriam Preissmann, Cléophée Robin, Nicolas Trotignon
A graph G is prismatic if for every triangle T of G, every vertex of G not in T has a unique neighbour in T. The complement of a prismatic graph is called \emph{antiprismatic}. The…
The independent set problem is FPT for even-hole-free graphs
Edin Husic, Stephan Thomasse, Nicolas Trotignon
The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theore…
(Theta, triangle)-free and (even hole, )-free graphs. Part 1 : Layered wheels
Ni Luh Dewi Sintiari, Nicolas Trotignon
We present a construction called layered wheel. Layered wheels are graphs of arbitrarily large treewidth and girth. They might be an outcome for a possible theorem characterizing g…
Coloring graphs with no induced subdivision of
Louis Esperet, Nicolas Trotignon
Let be the 5-vertex graph obtained from , the complete graph on four vertices, by subdividing one edge precisely once (i.e. by replacing one edge by a path on three ve…