56 citations · 715 across the 68 of their papers we have counts for
70 papers
(Even hole, triangle)-free graphs revisited
Beatriz Martins, Nicolas Trotignon
We revisit a classical paper about (even hole, triangle)-free graphs [Conforti, Cornuéjols, Kapoor and Vu\v sković, Triangle-free graphs that are signable without even holes, Journ…
Induced Disjoint Paths Without an Induced Minor
Pierre Aboulker, Édouard Bonnet, Timothé Picavet +1
We exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs -- which avoids the 1-subdivis…
Unavoidable induced subgraphs in graphs with complete bipartite induced minors
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen +2
We prove that if a graph contains the complete bipartite graph as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. W…
Induced Minor Models. I. Structural Properties and Algorithmic Consequences
Nicolas Bousquet, Clément Dallard, Maël Dumas +4
A graph is said to be an induced minor of a graph if can be obtained from by a sequence of vertex deletions and edge contractions. Equivalently, is an induced m…
Graphs without a 3-connected subgraph are 4-colorable
Édouard Bonnet, Carl Feghali, Tung Nguyen +4
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best…
A tamed family of triangle-free graphs with unbounded chromatic number
Édouard Bonnet, Romain Bourneuf, Julien Duron +3
We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every non-trivial graph either contains a pair of non-adjacent twins or has an edg…
When all holes have the same length
Jake Horsfield, Myriam Preissmann, Cléophée Robin +3
For every integer , we give a structural description of the class of graphs whose chordless cycles of length at least 4 all have length .
Burling graphs revisited, part III: Applications to -boundedness
Pegah Pournajafi, Nicolas Trotignon
The Burling sequence is a sequence of triangle-free graphs of unbounded chromatic number. The class of Burling graphs consists of all the induced subgraphs of the graphs of this se…
Graphs with all holes the same length
Linda Cook, Jake Horsfield, Myriam Preissmann +5
A graph is "-holed" if all its induced cycles of length at least four have length exactly . We give a complete description of the -holed graphs for each $\ell\ge…
Burling graphs revisited, part II: Structure
Pegah Pournajafi, Nicolas Trotignon
The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Any graph which is an induced subgraph of a graph in this sequence is called a Burling gr…
Burling graphs revisited, part I: New characterizations
Pegah Pournajafi, Nicolas Trotignon
The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Each of them is isomorphic to the intersection graph of a set of axis-parallel boxes in $…
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…
Graphs with polynomially many minimal separators
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +3
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the…
(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…
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…
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…
The (theta, wheel)-free graphs Part III: cliques, stable sets and coloring
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 paths between the same pair of distinct vertices so that the union of any two of the…
Triangle-free graphs that do not contain an induced subdivision of are 3-colorable
Maria Chudnovsky, Chun-Hung Liu, Oliver Schaudt +3
We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vuskovic.