From the 2 of 9 linked papers with an AI index.
9 papers
Far-apart ErdÅs--Pósa property of long cycles
Maria Chudnovsky, Vida DujmoviÄ, Gwenaël Joret +4
The authors prove that for any graph, either it contains many cycles of length at least ℓ that are pairwise far apart, or a small vertex set can be removed to eliminate all such lo…
Adjacency labelling for proper minor-closed graph classes
Vida DujmoviÄ, Cyril Gavoille, Gwenaël Joret +3
The paper proves that every proper minor‑closed class of graphs admits an adjacency labeling scheme using (1+o(1))·log₂ n bits, equivalently showing the existence of an n^{1+o(1)}‑…
3-Colouring Graphs Excluding a Fixed Minor
Vida DujmoviÄ, Hussein Houdrouge, Pat Morin
We show that, for every fixed graph , every -vertex graph that excludes as a minor is -colourable with clustering . That is, there exists a function…
ErdÅs--Pósa property of cycles that are far apart
Vida DujmoviÄ, Gwenaël Joret, Piotr Micek +1
We prove that there exist functions such that for all nonnegative integers and , for every graph , either contains cycles such that…
2-dimensional unit vector flows
Hussein Houdrouge, Bobby Miraftab, Pat Morin
We study -dimensional unit vector flows on graphs, that is, nowhere-zero flows that assign to each oriented edge a unit vector in . We give a new geometric charac…
Local certification of geometric graph classes
Oscar Defrain, Louis Esperet, Aurélie Lagoutte +2
The goal of local certification is to locally convince the vertices of a graph that satisfies a given property. A prover assigns short certificates to the vertices of the g…