73 citations · 785 across the 86 of their papers we have counts for
4 papers · 1 filter
Adjacency labelling for proper minor-closed graph classes
Vida Dujmović, Cyril Gavoille, Gwenaël Joret +3
We show that every proper minor-closed class of graphs admits a -bit adjacency labelling scheme. Equivalently, for every proper minor-closed class a…
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Michele Conforti, Samuel Fiorin, Tony Huynh +2
Consider the family of graphs without node-disjoint odd cycles, where is a constant. Determining the complexity of the stable set problem for such graphs is a lon…
Planar graphs have bounded queue-number
Vida Dujmović, Gwenaël Joret, Piotr Micek +3
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called lay…
A tight Erdős-Pósa function for wheel minors
Pierre Aboulker, Samuel Fiorini, Tony Huynh +3
Let denote the wheel on vertices. We prove that for every integer there is a constant such that for every integer and every graph , eit…