Seminar iz diskretne matematike

Vodji seminarja: Boštjan Brešar in Sandi Klavžar
Predavanja potekajo ob ponedeljkih ob 15:15 v seminarski sobi P1 (Gosposvetska cesta 84, v 4. nadstropju).

Bodoča predavanja

Minula predavanja

Portier and Versteegen’s proof of the 3/4-conjecture

16. 01. 2023

Predavateljica: Vesna Iršič

Povzetek: Recently, Portier and Versteegen proved the 3/4-conjecture for the total domination game which states that for every graph $G$ without isolated vertices or edges, the game total domination number is at most $\frac{3}{4} |V(G)|$. In this talk, the outline of the proof will be presented.

Asymmetrizing infinite trees

17. 10. 2022

Predavatelj: Wilfried Imrich (about joint work with Florian Lehner, Rafal Kalinowski, Monika Pilsniak and Marcin Stawiski)

Povzetek: The talk is a continuation of the seminar talk of November 12, 2018 about automorphism breaking of countable trees. One says a tree, or more generally a graph,  is asymmetrizable if there exists a 2-coloring of its vertices that is only preserved by the identity automorphism. The talk outlines a proof that each infinite tree whose degrees are bounded by 2^m, where m is an arbitrary infinite cardinal, is asymmetrizable if all non-identity automorphisms move at least m vertices.

The talk begins with a few remarks about infinite cardinals, successor cardinals, regular and singular cardinals, the Generalized Continuum Hypothesis, results of Babai, Sabidussi and Polat and then presents the main result.

Graph Polynomials

28. 03. 2022

Predavateljica: Aysel Erey (Gebze Technical University, Turčija)

Vsi seminarji
Accessibility