Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije

Raziskovalni matematični seminar - Arhiv

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: 30.6.20
(10:00 -- 11:00)
Predavalnica / Location: ZOOM (See link below)
Predavatelj / Lecturer: Micael Toledo
Naslov / Title: Cubic vertex-transitive graphs admitting a group of automorphisms with few orbits.
Vsebina / Abstract:

Highly symmetric graphs are frequently studied in terms of the action of a specific type of group of automorphisms, as their structure is often completely determined by this action. Such is the case of  a graph G admitting a group of automorphism X that acts transitively on its the arcs, or regularly on its vertices. If X is not vertex-transitive but partitions the vertex-set of G into orbits of equal size, then G can be (and usually is) studied through the theory of covering graphs. However, the case where X partitions the vertex-set of G into few orbits of different sizes is much less understood, and many of the classical tools used in the previously mentioned cases fall short. We give a general overview of the subject, and present new tools and possible lines of research to tackle the problem of classifying cubic graphs admitting a group of automorphisms with a few orbits (possibly of different sizes). We focus particularly on those graphs whose full automorphism group is transitive.


Link for the videoconference:



Datum in ura / Date and time: 15.6.20
(10:00 -- 11:00)
Predavalnica / Location: FAMNIT-MP7
Predavatelj / Lecturer: ANDREA MUNARO (Queen's University, Belfast, United Kingdom)
Naslov / Title: Width parameters and graph classes: the case of mim-width
Vsebina / Abstract:

 Many computationally hard graph problems can be solved efficiently after placing appropriate restrictions on the input graphs. One reason that might explain this jump in complexity is that the class of restricted inputs has bounded "width". There are several ways of defining a notion of "width", giving rise for example to well-known width parameters such as tree-width and clique-width.

In the talk, I will focus on the width parameter mim-width, introduced by Vatshelle. The modelling power of mim-width is stronger than that of clique-width, in the sense that graphs of bounded clique-width have bounded mim-width but there exist graph classes with bounded mim-width and unbounded clique-width. I will overview structural properties and algorithmic applications of this parameter and present recent joint work with Nick Brettell, Jake Horsfield, Giacomo Paesani and Daniël Paulusma.

The seminar was held by Zoom. 

The slides of the talk are available in pdf at this link.