Raziskovalni matematični seminar - Arhiv
| 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
We show that, for every $n$ and every surface $\Sigma$ (orientable or not), there is a graph $U$ embeddable on $\Sigma$ with at most $c n^2$ vertices that contains as minor every graph embeddable on $\Sigma$ with
$n$ vertices. The constant $c$ depends polynomially on the Euler genus of $\Sigma$. This generalizes a well-known result for planar graphs due to Robertson, Seymour, and Thomas [\textit{Quickly Excluding a Planar
Graph.} J. Comb. Theory B, 1994] which states that the square grid on $4n^2$ vertices contains as minor every planar graph with $n$ vertices.
This is a joint work with Cyril Gavoille.
Everyone is welcome and
We present a new simple construction of graphs with high odd girth (length of a shortest odd cycle) and high chromatic number. This is a joint work with Édouard Bonnet, Romain Bourneuf, Julien Duron, Colin Geniet and Stéphan Thomassé.
Everyone is welcome and encouraged to attend.
