From the 1 of 4 linked papers with an AI index.
4 papers
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)}‑…
Planar graphs in blowups of fans
Marc Distel, Vida DujmoviÄ, Gwenaël Joret +3
We show that every -vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order . Equivalently,…
3-Colouring Planar Graphs
Vida DujmoviÄ, Pat Morin, Sergey Norin +1
We show that every -vertex planar graph is 3-colourable with monochromatic components of size . The best previous bound was due to Linial, MatouÅ¡ek, Sh…
Grid Minors and Products
Vida DujmoviÄ, Pat Morin, David R. Wood +1
Motivated by recent developments regarding the product structure of planar graphs, we study relationships between treewidth, grid minors, and graph products. We show that the Carte…