7 papers · 1 filter
Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
Julien Duron, Nikolas Mählmann, Szymon ToruÅczyk
A graph class is -WQO if its -labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is -…
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…
On the minimum number of inversions to make a digraph -(arc-)strong
Julien Duron, Frédéric Havet, Florian Hörsch +1
The {\it inversion} of a set of vertices in a digraph consists of reversing the direction of all arcs of . We study (resp. ) whic…
Counterexamples to statements on isometric graph coverings
Paul Bastide, Julien Duron, JÄdrzej Hodor +2
A connected subgraph of a graph is isometric if it preserves distances. In this short note, we provide counterexamples to several variants of the following general question: When a…
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…
Long induced paths in sparse graphs and graphs with forbidden patterns
Julien Duron, Louis Esperet, Jean-Florent Raymond
Consider a graph with a path of order . What conditions force to also have a long induced path? As complete bipartite graphs have long paths but no long induced path…