Seminár z teórie grafov - Jan Goedgebeur (19.6.2018)

mimoriadne v utorok 19.6.2018 o 15:00 hod. v miestnosti M/213

13. 06. 2018 10.09 hod.
Od: Martin Škoviera

Prednášajúci: Jan Goedgebeur (University of Ghent, Belgium)

Názov: Bounds for the smallest k-chromatic graphs of given girth

Termín: 19.6.2018, 15:00 hod., M/213

Abstrakt:
A graph with chromatic number k is called k-chromatic. Using computational methods, we show that the smallest triangle-free 6-chromatic graphs have at least 32 and at most 40 vertices.
We also determine the complete set of all triangle-free 5-chromatic graphs up to 23 vertices and all triangle-free 5-chromatic graphs on 24 vertices with maximum degree at most 7. This implies that Reed's conjecture holds for triangle-free graphs up to at least 24 vertices. Next to that, we determine that the smallest regular triangle-free 5-chromatic graphs have 24 vertices. Finally, we show that the smallest 5-chromatic graphs of girth at least 5 have at least 29 vertices and that the smallest 4-chromatic graphs of girth at least 6 have at least 25 vertices.