56 citations · 270 across the 25 of their papers we have counts for
26 papers
Bisimplicial separators
Martin Milanič, Irena Penev, Nevena Pivač +1
A minimal separator of a graph is a set such that there exist vertices with the property that separates from in , b…
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 .
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…
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…
Counting weighted independent sets beyond the permanent
Martin Dyer, Mark Jerrum, Haiko Muller +1
Jerrum, Sinclair and Vigoda (2004) showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition…
Coloring rings
Frédéric Maffray, Irena Penev, Kristina Vušković
A ring is a graph whose vertex set can be partitioned into nonempty sets, , such that for all , the set can be ordered as…
Clique-cutsets beyond chordal graphs
Valerio Boncompagni, Irena Penev, Kristina Vuskovic
Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and…
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.
The (theta, wheel)-free graphs Part II: structure theorem
Marko Radovanović, Nicolas Trotignon, Kristina Vušković
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 paths induces a hole. A wheel is a graph formed by a hole an…
Structure and algorithms for (cap, even hole)-free graphs
Kathie Cameron, Murilo V. G. da Silva, Shenwei Huang +1
A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with…
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…
Coloring Square-free Berge Graphs
Maria Chudnovsky, Irene Lo, Frederic Maffray +2
We consider the class of Berge graphs that do not contain a chordless cycle of length . We present a purely graph-theoretical algorithm that produces an optimal coloring in poly…
The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
Emilie Diot, Marko Radovanović, Nicolas Trotignon +1
Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for heredit…
On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph
Nicolas Trotignon, Kristina Vušković
We prove a decomposition theorem for the class of triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove tha…
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…
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…
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…
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.…
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…
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…
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.