56 citations · 715 across the 68 of their papers we have counts for
13 papers · 2 filters
Parameterized algorithm for weighted independent set problem in bull-free graphs
Stéphan Thomassé, Nicolas Trotignon, Kristina Vusković
The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph…
Complexity of colouring problems restricted to unichord-free and \{square,unichord\}-free graphs
Raphael C. S. Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
A \emph{unichord} in a graph is an edge that is the unique chord of a cycle. A \emph{square} is an induced cycle on four vertices. A graph is \emph{unichord-free} if none of its ed…
Detecting an induced net subdivision
Maria Chudnovsky, Paul Seymour, Nicolas Trotignon
A {\em net} is a graph consisting of a triangle and three more vertices, each of degree one and with its neighbour in , and all adjacent to different vertices of . We giv…
Edge-colouring and total-colouring chordless graphs
Raphael C. S. Machado, Celina M. H. de Figueiredo, Nicolas Trotignon
A graph is \emph{chordless} if no cycle in has a chord. In the present work we investigate the chromatic index and total chromatic number of chordless graphs. We describe a…
Graphs that do not contain a cycle with a node that has at least two neighbors on it
Pierre Aboulker, Marko Radovanović, Nicolas Trotignon +1
We recall several known results about minimally 2-connected graphs, and show that they all follow from a decomposition theorem. Starting from an analogy with critically 2-connected…
Finding an induced subdivision of a digraph
Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon
We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) , does it contain an induced subdivision of a prescribed digraph ? The c…
Combinatorial optimization with 2-joins
Nicolas Trotignon, Kristina Vušković
A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs.…
The four-in-a-tree problem in triangle-free graphs
Nicolas Derhy, Christophe Picouleau, Nicolas Trotignon
The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time whether three given vertices of a graph belong to an induced tree. Here, we study four-in-a-tree fo…
Detecting induced subgraphs
Benjamin Lévêque, David Y. Lin, Frédéric Maffray +1
An \emph{s-graph} is a graph with two kinds of edges: \emph{subdivisible} edges and \emph{real} edges. A \emph{realisation} of an s-graph is any graph obtained by subdividing s…
Algorithms for square--free Berge graphs
Frédéric Maffray, Nicolas Trotignon, Kristina Vušković
We consider the class of graphs containing no odd hole, no odd antihole, and no configuration consisting of three paths between two nodes such that any two of the paths induce a ho…
Algorithms for perfectly contractile graphs
Frédéric Maffray, Nicolas Trotignon
We consider the class of graphs that contain no odd hole, no antihole of length at least 5, and no "prism" (a graph consisting of two disjoint triangles with three disjo…
Coloring perfect graphs with no balanced skew-partitions
Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck +1
We present an algorithm that computes a maximum stable set of any perfect graph with no balanced skew-partition. We present time algorithm that colors them.
Detecting wheels
Emilie Diot, Sébastien Tavenas, Nicolas Trotignon
A \emph{wheel} is a graph made of a cycle of length at least~4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a…