The goal of the project Flows and cycles in graphs on surfaces is to investigate the topic of flows in graphs drawn on surfaces, motivated by applications in graph coloring and a possible approach towards the Cycle Double Cover conjecture. Moreover, we develop the algebraic connection via the study of the surface Tutte polynomial.
The project is funded in years 2022–24 by standard grant 22-17398S of Czech Science Foundation.
Project team:
- Zdeněk Dvořák (principal investigator)
- Robert Šámal (senior researcher)
- Andrew Goodall (senior researcher)
- Fariba Noorizadeh (doctoral student)
- Babak Ghanbari (doctoral student)
- Guillermo Gamboa (doctoral student)
- Ben Moore (postdoc, 2022–23)
- Guillaume Aubian (postdoc, 2023–24)
Selected publications:
- Z. Dvořák, B. Mohar: On density of Z3-flow-critical graphs, SIAM J. Discrete Math. 37 (2023), 699--717.
- C. Bang, Z. Dvořák, E. Heath, B. Lidický: Embedded graph 3-coloring and Flows, preprint.
- Z. Dvořák, B. Moore, J.-S. Sereni: 3-coloring graphs on non-orientable surfaces using nowhere-zero flows, in preparation.
- Z. Dvořák: A strengthening and an efficient implementation of Alon-Tarsi list coloring method, preprint.
- Z. Dvořák, C. Feghali: Solution to a problem of Grünbaum on the edge density of 4-critical planar graphs, preprint.
- B. Ghanbari, D. Hartman, V. Jelínek, A. Pokorná, R. Šámal, P. Valtr: On the structure and values of betweenness centrality in dense betweenness-uniform graphs, In European Conference on Combinatorics, Graph Theory and Applications, no. 12 (2023).