56 citations · 715 across the 68 of their papers we have counts for
24 papers · 1 filter
On the tree-width of even-hole-free graphs
Pierre Aboulker, Isolde Adler, Eun Jung Kim +2
The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, )-free graphs was constructed, that still…
A class of graphs with large rankwidth
Chính Hoàng, Nicolas Trotignon
We describe several graphs with arbitrarily large rankwidth (or equivalently with arbitrarily large cliquewidth). Korpelainen, Lozin, and Mayhill [Split permutation graphs, Graphs…
(Theta, triangle)-free and (even hole, )-free graphs. Part 2 : bounds on treewidth
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé +1
A {\em theta} is a graph made of three internally vertex-disjoint chordless paths , , of length at least~2 and such that no edge…
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…
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…
(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…
Connected greedy colouring in claw-free graphs
Ngoc Khang Le, Nicolas Trotignon
An ordering of the vertices of a graph is \emph{connected} if every vertex (but the first) has a neighbor among its predecessors. The greedy colouring algorithm of a graph with a c…
On rank-width of even-hole-free graphs
Isolde Adler, Ngoc Khang Le, Haiko Müller +3
We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because cho…
-bounds, operations and chords
Lan Anh Pham, Nicolas Trotignon
A \emph{long unichord} in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is \emph{long-unichord-free} if it does not contain any long-unich…
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…
Vertex elimination orderings for hereditary graph classes
Pierre Aboulker, Pierre Charbit, Nicolas Trotignon +1
We provide a general method to prove the existence and compute efficiently elimination orderings in graphs. Our method relies on several tools that were known before, but that were…
Coloring Artemis graphs
Benjamin Lévêque, Frédéric Maffray, Bruce Reed +1
We consider the class A of graphs that contain no odd hole, no antihole, and no ``prism'' (a graph consisting of two disjoint triangles with three disjoint paths between them). We…