56 citations · 715 across the 68 of their papers we have counts for
17 papers · 2 filters
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…
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…
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…
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…
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…
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.
On the structure of self-complementary graphs
Nicolas Trotignon
A \emph{self-complementary} graph is a graph isomorphic to its complement. An isomorphism between and its complement, viewed as a permutation of , is then called an \emph…
Ramsey-type results on singletons, co-singletons and monotone sequences in large collections of sets
Sylvain Gravier, Frédéric Maffray, Jérôme Renault +1
We say that a 0-1 matrix of size can be found in a collection of sets if we can find sets in and elements $…
Complements of nearly perfect graphs
András Gyárfás, Zhentao Li, Raphael Machado +3
A class of graphs closed under taking induced subgraphs is -bounded if there exists a function such that for all graphs in the class, . We consider th…
Substitution and -Boundedness
Maria Chudnovsky, Irena Penev, Alex Scott +1
A class of graphs is said to be {\em -bounded} if there is a function such that for all and all induced s…
Perfect graphs: a survey
Nicolas Trotignon
Perfect graphs were defined by Claude Berge in the 1960s. They are important objects for graph theory, linear programming and combinatorial optimization. Claude Berge made a conjec…