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

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

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

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