Flows and cycles in graphs on surfaces
Project goals
Flows in graphs have a long and rich history in combinatorial theory. In his influential paper, Tutte introduced the concept of nowhere-zero flows motivated by the duality to graph colorings in plane graphs. Nowhere-zero flows rose to prominence in part due to their connections to other important topics such as the Cycle Double Cover conjecture and Berge–Fulkerson conjecture. The importance of the topic is further reinforced through algebraic connections, in particular through the Tutte polynomial which enumerates flows and relates them to other graph invariants when evaluated at suitable points. Much of the research into nowhere-zero flows is inspired by Tutte's insightful conjectures and focuses on general graphs. In this project, we 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.
Keywords
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202200004
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
22-17398S
Alternative language
Project name in Czech
Toky a cykly v grafech na plochách
Annotation in Czech
Toky v grafech jsou historicky jedním z centrálních témat kombinatoriky. Nikde-nulové toky byly zavedeny ve vlivném článku W. Tutteho jakožto duální koncept ke grafové barevnosti, a k jejich význačnosti přispěly i další souvislosti, například s hypotézou o dvojitém pokrytí cykly a Berge-Fulkersonovou hypotézou, či algebraické propojení s dalšími grafovými parametry přes Tutteho polynom. Většina výzkumu týkajícího se nikde-nulových toků je inspirována Tutteho hypotézami a zaměřuje se na toky v obecných grafech. V tomto projektu budeme studovat toky v grafech na plochách, což je motivováno aplikacemi v grafové barevnosti a ve slibném přístupu k hypotéze o dvojitém pokrytí cykly. Zaměříme se také na algebraické souvislosti a rozvineme teorii plochového Tutteho polynomu.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10101 - Pure mathematics
OECD FORD - secondary branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BA - General mathematics
BC - Theory and management systems
BD - Information theory
IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2022
Realization period - end
Dec 31, 2024
Project status
—
Latest support payment
Feb 29, 2024
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP25-GA0-GA-R
Data delivery date
Mar 12, 2025
Finance
Total approved costs
10,780 thou. CZK
Public financial support
9,743 thou. CZK
Other public sources
1,037 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
10 780 CZK thou.
Public support
9 743 CZK thou.
90%
Provider
Czech Science Foundation
OECD FORD
Pure mathematics
Solution period
01. 01. 2022 - 31. 12. 2024