73 citations · 785 across the 86 of their papers we have counts for
3 papers · 2 filters
First-Fit is Linear on Posets Excluding Two Long Incomparable Chains
Gwenaël Joret, Kevin G. Milans
A poset is (r + s)-free if it does not contain two incomparable chains of size r and s, respectively. We prove that when r and s are at least 2, the First-Fit algorithm partitions…
Small Minors in Dense Graphs
Samuel Fiorini, Gwenaël Joret, Dirk Oliver Theis +1
A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra pr…
Trees with Given Stability Number and Minimum Number of Stable Sets
Véronique Bruyère, Gwenaël Joret, Hadrien Mélot
We study the structure of trees minimizing their number of stable sets for given order and stability number . Our main result is that the edges of a non-trivial extremal tre…