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

Distinguishing trees and subcubic graphs

06. 03. 2017

Predavatelj: Wilfried Imrich

Abstract: Thomas Tucker’s infinite motion conjecture asserts that the vertices of every connected, locally finite graph G can be colored with 2 colors such that the identity automorphism is the only automorphism that respects the coloring under the condition that every automorphism moves infinitely many vertices. We say G is 2-distinguishable if it has infinite motion.

The conjecture is true for many classes of graphs, but it is not known whether it holds for graphs with given maximum degree k, unless k=3.
Such graphs are called subcubic. However, there is evidence that infinite motion is not needed for subcubic graphs and that one can always find a 2-coloring that fixes all vertices with the exception of at most two pairs of interchangeable vertices. We show that this is true for trees, subcubic graphs without small cycles and vertex transitive cubic graphs.

In particular, we show that every subcubic infinite tree is 2-distinguishable and that every finite subcubic tree has a 2-coloring, which fixes all vertices, with the possible exception of two vertices of degree 1 with a common neighbor. We also show that the only vertex or edge-transitive finite or infinite subcubic graphs are the K_4, the K_{3,3} or the cube.

For finite or infinite trees of maximum valence k we show that there is a 2-coloring that fixes all vertices that have no endvertex within distance log_2 k +1 .

Acknowledgement: This joint work with Thomas Lachmann and Gundelinde Wiegel (vertex transitive graphs), Svenja Hüning, Judith Kloas and Hannah Schreiber (trees) and Thomas Tucker.

Speaker: Wilfried Imrich and possibly one of the co-authors.

Vector connectivity in graphs

06. 06. 2016

Predavatelj: Martin Milanič

Motivated by challenges related to domination, connectivity, and information propagation in social and other networks, we study the Vector Connectivity problem. This problem, introduced by Boros et al. in 2013, takes as input a graph G and an integer r(v) for every vertex v of G, and the objective is to find a vertex subset S of minimum cardinality such that every vertex v either belongs to S, or is connected to at least r(v) vertices of S by disjoint paths. If we require each path to be of length exactly 1, we get the well-known vector domination problem, which is a generalization of the dominating set and vertex cover problems. Consequently, the vector connectivity problem becomes NP-hard if an upper bound on the length of the disjoint paths is also supplied as input. Due to the hardness of these domination variants even on restricted graph classes, like split graphs, Vector Connectivity seems to be a natural problem to study for drawing the boundaries of tractability for this type of problems.

In the talk, I will give an overview of known complexity results for the Vector Connectivity problem. In particular, the problem can be solved in polynomial time on split graphs, in addition to cographs and trees. On the other hand, the problem is NP-hard for planar line graphs and for planar bipartite graphs, APX-hard on general graphs, and can be approximated in polynomial time within a factor of ln(n) + 2 on all n-vertex graphs. Vertex covers and dominating sets in a graph G can be easily characterized as hitting sets of derived hypergraphs (of G itself, and of the closed neighborhood hypergraph of G, respectively). Using Menger’s Theorem, a similar characterization of vector connectivity sets can be derived.

Based on joint works with Endre Boros, Ferdinando Cicalese, Pinar Heggernes, Pim van ‘t Hof, and Romeo Rizzi.

On incidence colorings of graphs

14. 03. 2016

Predavatelj: Borut Lužar

An incidence in a graph $G$ is a pair $(v,e)$ where $v$
is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$. Two incidences $(v,e)$ and $(u,f)$ are adjacent if at least one of the
following holds: (1) $v = u$, (2) $e = f$, or (3) $vuin{e,f}$. An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. The originators conjectured
that every graph G admits an incidence coloring with at most Δ(G)+2 colors. The conjecture is false in general, but there are
many classes of graphs for which it holds. We will present the main
results from the field and introduce some of our recent ones. Namely,
we will focus on incidence coloring of Cartesian products of graphs
and subquartic graphs.

1-perfectly orientable graphs and graph products

18. 01. 2016

Predavateljica: Tatiana Romina Hartinger

A graph G is said to be 1-perfectly orientable (1-p.o. for short) if it admits an orientation such that the out-neighborhood of every vertex is a clique in G. The class of 1-p.o. graphs forms a common generalization of the classes of chordal and circular arc graphs. Even though 1-p.o. graphs can be recognized in polynomial time, no structural characterization of 1-p.o. graphs is known. In this paper we consider the four standard graph products: the Cartesian product, the strong product, the direct product, and the lexicographic product. For each of them, we characterize when a nontrivial product of two graphs is 1-p.o.
Based on joint work with Martin Milanič (University of Primorska).
Vsi seminarji
Accessibility