24 citations · 100 across the 34 of their papers we have counts for
7 papers · 1 filter
The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
Pierre Aboulker, Rohan Kapadia
A special case of a theorem of De Bruijn and Erdős asserts that any noncollinear set of points in the plane determines at least distinct lines. Chen and Chvátal conjectured…
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…
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…
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…
Number of lines in hypergraphs
Pierre Aboulker, Adrian Bondy, Xiaomin Chen +3
Chen and Chvátal introduced the notion of lines in hypergraphs; they proved that every 3-uniform hypergraph with vertices either has a line that consists of all vertices or…
Excluding cycles with a fixed number of chords
Pierre Aboulker 'and' Nicolas Bousquet
Trotignon and Vuskovic completely characterized graphs that do not contain cycles with exactly one chord. In particular, they show that such a graph G has chromatic number at most…