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 |
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:
https://us02web.zoom.us/j/83916090638?pwd=Q3lkanVFZVhRTStnVW9Edi9lRmJhdz09
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.
