Navigation

Jump to main content
Thomas Jahn
SEG 25

25th SEG Workshop at TU Chemnitz

South Eastern Germany Workshop on Combinatorics, Graph Theory, and Algorithms
By attending the workshop, you accept the terms and conditions for events at Chemnitz University of Technology. (deutsche Version)

Time and Venue

The workshop will start on Tuesday, October 22, at 15:00 in room N113 of the Central Lecture Hall Building, Reichenhainer Straße 90, 09126 Chemnitz, and conclude with a joint dinner the same day.

Travel information

To get from Chemnitz main station to the Central Lecture Hall Building, take tram 3, C13, C14 or C15 to Technopark at platforms 1 to 4. Get off at TU Campus. Tickets are sold by CVAG ticket machines and bus drivers. Single tickets cost 2.20 Euro; they are valid for one trip to a particular stop and for one hour. Day passes cost 4.40 Euro; they are valid the whole day. Using these tickets, you are allowed to transfer to other bus and tram lines in Chemnitz within the validity period. Single tickets and day passes are already stamped and are immediately valid.

Participants

Maryam AlipourMittweida
Christoph BrauseFreiberg
Maximilian GeißerFreiberg
Frank GöringChemnitz
Anja HähleChemnitz
Tobias HofmannChemnitz
Carlos HoppenPorto Alegre
Hany IbrahimMittweida
Thomas JahnChemnitz
Hanno LefmannChemnitz
Horst MartiniChemnitz
Knut OdermannChemnitz
Ingo SchiermeyerFreiberg
Dionatan SchmidtChemnitz
Martin SonntagFreiberg
Peter TittmannMittweida
Margit VoigtDresden
Martin WinterChemnitz

Scientific Program

Time Speaker Title & Abstract
15:00 Workshop opening
15:10 Maximilian Geißer

A graph \(G\) with clique number \(\omega(G)\) and chromatic number \(\chi(G)\) is perfect if \(\chi(H) = \omega(H)\) for every induced subgraph \(H\) of \(G\). As a generalisation of this concept a family \(G\) of graphs is called \(\chi\)-bounded with binding function \(f\) if for each \(G\in\mathcal{G}\) and each induced subgraph \(G^\prime\) of \(G\) the condition \(\chi(G^\prime)\leq f(\omega(G^\prime))\) holds. It is still an open question whether there is a polynomial \(\chi\)-binding function for the family of \(P_5\)-free graph. For several classes which occur by forbidding an additional small graph as an induced subgraph polynomial \(\chi\)-binding functions have been shown (cf. [1, 2]). In this talk we will report about some new upper bounds for the chromatic number of \((P_5,H)\)-free graphs, where \(H\in\{\text{banner, dart, gem, hammer}\}\). All these bounds are optimal \(\chi\)-binding functions. (Joint work with C. Brause and I. Schiermeyer.)

[1] I. Schiermeyer, Chromatic number of \(P_5\)-free graphs: Reed’s conjecture, Discrete Mathematics 339 (7) (2016) 1940–1943.

[2] I. Schiermeyer and B. Randerath, Polynomial \(\chi\)-binding functions and forbidden induced subgraphs: a survey, Graphs and Combinatorics 35 (1) (2019) 1–31.

15:45 Martin Winter

It has long been known that there are five regular polyhedra (the Platonic solids), six regular \(4\)-polytopes and exactly three regular \(d\)-polytopes for all \(d\geq 5\). Hence, the symmetry requirement of regularity (aka flag-transitivity) seems to be quite restrictive for convex polytopes. In contrast, the class of vertex-transitive polytopes (all vertices are identical under the symmetries of the polytope) is almost as rich as the finite groups. In this talk we ask about the class of edge-transitive (convex) polytopes, that is, polytopes in which all edges are identical under the symmetries of the polytope. Despite this restriction feeling more similar to vertex-transitivity than to regularity, we will see that quite the contrary seems to be the case: the class of edge-transitive polytopes appears to be quite restricted. We give, what we believe to be, a complete list of all edge-transitive polytopes, as well as a full classification for certain interesting sub-classes. Thereby, we show how edge-transitive polytopes can be studied with the tools of spectral graph theory. We close by listing possible consequences of a proof of classifications, e.g. for matroid theory.

16:20 Coffee break
16:40 Knut Odermann

The Heilbronn triangle problem is to choose \(n\) points from the unit-square \([0,1]^2\) in such a way that any triangle of smallest area induced by any three of the \(n\) points has an area that is as large as possible. More generally, given \(n\) points \(P_1,\ldots,P_n\) in the \(d\)-dimensional unit-cube \([0,1]^d\), let \(V_{k,\min}^{(d)}(P_1,\ldots,P_n)\) denote the minimum of the volumes of the convex hulls of any \(k\) of the points \(P_1,\ldots,P_n\), where \(d,k \geq 2\). The aim is to find the supremum of \(V_{k,\min}^{(d)}(P_1,\ldots,P_n)\), which is difficult and the solution to this problem is unknown. Instead, in this talk we investigate the expected value of \(V_{k,\min}^{(d)}(P_1,\ldots,P_n)\) when \(P_1,\ldots,P_n\) are randomly and independently chosen in \([0,1]^d\) according to the uniform distribution. (Joint work with F. Benevides, C. Hoppen, and H. Lefmann.)

17:15 Christoph Brause

It is well known that the clique number \(\omega(G)\) of a graph \(G\) is a lower bound on the chromatic number \(\chi(G)\). Considering upper bounds on \(\chi(G)\) in terms of \(\omega(G)\), we come to the concept of \(\chi\)-binding functions. In particular, a function \(f:\mathbb{N}\to\mathbb{N}\) with \(\chi(G)\leq f(\omega(G))\) for each graph \(G\) of a (hereditary) graph class \(\mathcal{G}\) is called \(\chi\)-binding function for \(\mathcal{G}\). Since more than three decades, finding such functions for graph classes is a hot topic in chromatic graph theory. In the last years, the attention was drawn to graph classes defined by forbidden induced subgraphs. In this talk, we survey results of [1,2,3] continuing the study of \(\chi\)-binding functions for graph classes defined by forbidden induced subgraphs, and discuss the phenomenon that the independence number has a massive impact on the order of magnitude of best-possible \(\chi\)-binding functions.

[1] C. Brause, D.T. Doan, P. Holub, A. Kabela, Z. Ryjáček, I. Schiermeyer, and P. Vrána, Forbidden induced subgraphs and perfectness for claw-free graphs of independence at least \(4\), manuscript.

[2] C. Brause, M. Geißer, and I. Schiermeyer, Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions, manuscript.

[3] C. Brause, P. Holub, A. Kabela, Z. Ryjáček, I. Schiermeyer, and P. Vrána, On forbidden induced subgraphs for \(K_{1,3}\)-free graphs, Discrete Mathematics 342 (2019), 1602–1608.

18:00 Walk from the Central Lecture Hall Building to the city center
18:45 Workshop Dinner at Cortina
Here is the program in pdf format.

Workshop Dinner

At Cortina, Straße der Nationen 12, 09111 Chemnitz, starting at 18:45. To get there from the Central Lecture Hall Building, go can join the walking group or go to the tram stop TU Campus and take tram 3 to Hauptbahnhof, C13 to Burgstädt, C14 to Mittweida, or C15 to Hainichen and get off at Roter Turm. From there, you should see the restaurant.

Map with walking directions