10 citations · 19 across the 4 of their papers we have counts for
6 papers
Well-quasi-ordering H-contraction-free graphs
Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck
A well-quasi-order is an order which contains no infinite decreasing sequence and no infinite collection of incomparable elements. In this paper, we consider graph classes defined…
Induced minors and well-quasi-ordering
Jarosław Błasiok, Marcin Kamiński, Jean-Florent Raymond +1
A graph is an induced minor of a graph if it can be obtained from an induced subgraph of by contracting edges. Otherwise, is said to be -induced minor-free. Robi…
Multigraphs without large bonds are wqo by contraction
Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck
We show that the class of multigraphs with at most connected components and bonds of size at most is well-quasi-ordered by edge contraction for all positive integers .…
Clique-Stable Set separation in perfect graphs with no balanced skew-partitions
Aurélie Lagoutte, Théophile Trunck
Inspired by a question of Yannakakis on the Vertex Packing polytope of perfect graphs, we study the Clique-Stable Set Separation in a non-hereditary subclass of perfect graphs. A c…
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…
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.