25th SEG Workshop at TU Chemnitz
South Eastern Germany Workshop on Combinatorics, Graph Theory, and AlgorithmsTime 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 Alipour  Mittweida 
Christoph Brause  Freiberg 
Maximilian Geißer  Freiberg 
Frank Göring  Chemnitz 
Anja Hähle  Chemnitz 
Tobias Hofmann  Chemnitz 
Carlos Hoppen  Porto Alegre 
Hany Ibrahim  Mittweida 
Thomas Jahn  Chemnitz 
Hanno Lefmann  Chemnitz 
Horst Martini  Chemnitz 
Knut Odermann  Chemnitz 
Ingo Schiermeyer  Freiberg 
Dionatan Schmidt  Chemnitz 
Martin Sonntag  Freiberg 
Peter Tittmann  Mittweida 
Margit Voigt  Dresden 
Martin Winter  Chemnitz 
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.)

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 flagtransitivity) seems to be quite restrictive for convex polytopes. In contrast, the class of vertextransitive 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 edgetransitive (convex) polytopes, that is, polytopes in which all edges are identical under the symmetries of the polytope. Despite this restriction feeling more similar to vertextransitivity than to regularity, we will see that quite the contrary seems to be the case: the class of edgetransitive polytopes appears to be quite restricted. We give, what we believe to be, a complete list of all edgetransitive polytopes, as well as a full classification for certain interesting subclasses. Thereby, we show how edgetransitive 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 unitsquare \([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 unitcube \([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 bestpossible \(\chi\)binding functions.

18:00  Walk from the Central Lecture Hall Building to the city center  
18:45  Workshop Dinner at Cortina 