Springe zum Hauptinhalt
Fakultät für Informatik


296. Informatik-Kolloquium

Professur Theoretische Informatik und Informationssicherheit


Prof. Dr. Fabricio Benevides

Universidade Federal do Ceará
Fortaleza, Brasilien

"Counting Gallai k-colorings"

Mittwoch, 08.05.2019
15:30 Uhr, Straße der Nationen 62, Böttcher-Bau, 1/273 (neu: A10.273)

Alle interessierten Personen sind herzlich eingeladen!


A Gallai k-coloring is a coloring of the edges of complete graph using k colors such that every triangle has at least two edges with the same color, that is, there are no rainbow triangles. We show an asymptotically sharp bound for the number of Gallai k-colorings, even for the case where k is exponentially large with respect to the number of vertices of the graph. If time permits, we will also discuss some previous techniques for the (related but no equivalent) Erdos-Rothschild problem.