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)

Well-hued graphs

Predavateljica: Kirsti Kuenzel (Trinity College, Hartford, CT, ZDA)

A graph $G$ is called well-hued if for each positive integer $k$ there is an integer $a_k$ such that every maximal $k$-colorable subgraph of $G$ has order $a_k$. This notion of well-hued can be viewed as a generalization to the property of being well-covered. We say that $G$ is well-covered if every maximal independent set has the same cardinality, namely $\alpha(G)$. Thus, if a graph is well-hued, it is also well-covered for all maximal $1$-colorable subgraphs must have the same cardinality. In this talk, we will investigate those well-hued graphs that are either cubic, planar, a split graph, or a product graph.

Predavanje bo potekalo preko MS Teams.