5 papers
Decomposing tournaments into comparability graphs
Pierre Aboulker, Logan Crew, Julien Duron +7
In this note, we introduce the \emph{partial order decomposition number} of a digraph , denoted , defined as the minimum integer such that $A(D)=A(P_1)\cup\cdots\cup…
A note on distance-hereditary graphs whose complement is also distance-hereditary
Hugo Jacob
Distance-hereditary graphs are known to be the graphs that are totally decomposable for the split decomposition. We characterise distance-hereditary graphs whose complement is also…
Planar induced paths via a decomposition into non-crossing ordered graphs
Julien Duron, Hugo Jacob
In any graph, the maximum size of an induced path is bounded by the maximum size of a path. However, in the general case, one cannot find a converse bound, even up to an arbitrary…
On a tree-based variant of bandwidth and forbidding simple topological minors
Hugo Jacob, William Lochet, Christophe Paul
We obtain structure theorems for graphs excluding a fan (a path with a universal vertex) or a dipole () as a topological minor. The corresponding decompositions can be com…
Twin-width one
Jungho Ahn, Hugo Jacob, Noleen Köhler +3
We investigate the structure of graphs of twin-width at most , and obtain the following results: - Graphs of twin-width at most are permutation graphs. In particular they ha…