10 papers
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 -…
Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width
Ãdouard Bonnet, Maël Dumas, Julien Duron
For every , Max Independent Set admits a polynomial-time -approximation algorithm on -vertex graphs of effectively bounded twin-width [Bergé et…
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…
Moderately beyond clique-width: reduced component max-leaf and related parameters
Ãdouard Bonnet, Yeonsu Chang, Julien Duron +2
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…
Maximum Independent Set when excluding an induced minor: and
Ãdouard Bonnet, Julien Duron, Colin Geniet +2
Dallard, MilaniÄ, and Å torgel [arXiv '22] ask if for every class excluding a fixed planar graph as an induced minor, Maximum Independent Set can be solved in polynomial time,…
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…