56 citations · 715 across the 68 of their papers we have counts for
30 papers · 1 filter
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…
Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem
Maurice Pouzet, Hamza Si Kaddour, Nicolas Trotignon
We describe , the class of graphs such that and its complement are claw-free. With few exceptions, it is made of graphs who…
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…
On wheel-free graphs
Pierre Aboulker, Frédéric Havet, Nicolas Trotignon
A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3-connected graph that does not contain a wheel as a…
Linear balanceable and subcubic balanceable graphs
Pierre Aboulker, Marko Radovanović, Nicolas Trotignon +2
In [{Structural properties and decomposition of linear balanced matrices}, {\it Mathematical Programming}, 55:129--168, 1992], Conforti and Rao conjectured that every balanced bipa…
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…
On graphs with no induced subdivision of
Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon
We prove a decomposition theorem for graphs that do not contain a subdivision of as an induced subgraph where is the complete graph on four vertices. We obtain also a s…
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.…
Excluding induced subdivisions of the bull and related graphs
Maria Chudnovsky, Irena Penev, Alexander Scott +1
For any graph , let be the class of graphs with no induced subdivision of . It was conjectured in [A.D. Scott, Induced trees in graphs of large chromatic nu…
On Roussel-Rubio-type lemmas and their consequences
Nicolas Trotignon, Kristina Vušković
Roussel and Rubio proved a lemma which is essential in the proof of the Strong Perfect Graph Theorem. We give a new short proof of the main case of this lemma. In this note, we als…
A structure theorem for graphs with no cycle with a unique chord and its consequences
Nicolas Trotignon, Kristina Vušković
We give a structural description of the class of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected…
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…
Decomposing Berge graphs and detecting balanced skew partitions
Nicolas Trotignon
A hole in a graph is an induced cycle on at least four vertices. A graph is Berge if it has no odd hole and if its complement has no odd hole. In 2002, Chudnovsky, Robertson, Seymo…
Odd pairs of cliques
Michel Burlet, Frédéric Maffray, Nicolas Trotignon
A graph is Berge if it has no induced odd cycle on at least 5 vertices and no complement of induced odd cycle on at least 5 vertices. A graph is perfect if the chromatic number equ…
A class of perfectly contractile graphs
Frédéric Maffray, Nicolas Trotignon
We consider the class of graphs that contain no odd hole, no antihole, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between the…
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…
Wheel-free planar graphs
Pierre Aboulker, Maria Chudnovsky, Paul Seymour +1
A \emph{wheel} is a graph formed by a chordless cycle and a vertex not in that has at least three neighbors in . We prove that every 3-connected planar graph that do…
Structure of classes of graphs defined by forbidding induced subgraphs
Nicolas Trotignon
This document is the Habilitation Thesis (Habilitation à Diriger des Recherches) of Nicolas Trotignon. It presents his work in structural graph theory, from 2001 to 2009.
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.