Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
-->
SI | EN

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
Datum in ura / Date and time: 2.10.23
(15:00 -- 16:00)
Predavalnica / Location: Famnit MP1
Predavatelj / Lecturer: Claire Hilaire (UP FAMNIT, Slovenia)
Naslov / Title: Minor-Universal Graph for Graphs on Surfaces
Vsebina / Abstract:

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 encouraged to attend.
 


Datum in ura / Date and time: 20.9.23
(14:30-15:00)
Predavalnica / Location: FAMNIT-VP1
Predavatelj / Lecturer: Nicolas Trotignon (CNRS, École Normale Supérieure de Lyon, France)
Naslov / Title: Graphs of high odd girth and high chromatic number
Vsebina / Abstract:

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.