Graph colorings and flows: structure and applications
Project goals
The project belongs to the areas of structural and algorithmic graph theory and it aims at providing new knowledge on the structure and the existence of colorings and flows in graphs. The scope of the project also includes problems related to cycles in graphs and matroids and algorithmic applications of the studied objects, in particular, in the areas of the channel assignment problem and the multicommodity flows.The structural problems addressed by the project include the colorings of embedded graphs with constraints given by an embedding (cyclic, facial colorings), the structure of critical and list-critical graphs on surfaces, the Shortest Cycle Cover Conjecture, and circular and fractional relaxations of the known open problems on colorings and flows. The applications include the channel assignment problem, in particular the recently developed framework of real number graph labellings, and algorithms for multiroute and length-bounded flows.
Keywords
barevnost grafůgrafy na plocháchproblém přidělování frekvencítoky v grafech
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 12 (SGA02009GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
201/09/0197
Alternative language
Project name in Czech
Barevnost a toky v grafech: strukturální aspekty a aplikace
Annotation in Czech
Cílem projektu je prohloubit současnou úroveň znalostí o obyčejných, seznamových, cirkulárních a zlomkových obarveních a tocích v grafech, speciálně v grafech vnořených na plochy, o struktuře cyklů v grafech a matroidech, a o algoritmických aplikacích těchto objektů.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
CEP - another secondary branch
—
10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The project was excellent, both in terms of expertise and in terms of disbursement of funds.
Solution timeline
Realization period - beginning
Jan 1, 2009
Realization period - end
Dec 31, 2011
Project status
U - Finished project
Latest support payment
Apr 16, 2011
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
CEP12-GA0-GA-U/02:2
Data delivery date
May 2, 2016
Finance
Total approved costs
3,064 thou. CZK
Public financial support
3,064 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
3 064 CZK thou.
Public support
3 064 CZK thou.
100%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 2009 - 31. 12. 2011