Seminar of Graph Theory - Gil Puig Surroca (22.10.2026)
Thursday 22.10.2026 at 9:50, Lecture room M 213
Gil Puig Surroca:
Dichoosability of graphs with high choosability
Abstract:
A conjecture of Erdős and Neumann-Lara from 1979 says that, if every orientation of a graph G can be partitioned into k acyclic subgraphs, then the chromatic number of G is at most f(k), where f is a function that is independent of G. We will discuss the list version of this conjecture, and explain how it can be approached using ideas of Alon about the choosability of graphs with large minimum degree.
Joint work with Ararat Harutyunyan and Lucas Picasarri-Arrieta.