Graphs and mappings -- Algebraic properties of graphs
Project goals
Main two topics of the project are vector coloring and flows in graphs. The first of them exemplifies usage of semidefinite programming to approximate chromatic number, the goal of the project is to understand other aspects of this parameter, both structural and algorithmic ones. The other topic includes study of the cycle space of graphs--a linear-algebraic object that encodes many properties of the graph. Cycle-continuous mappings study graphs in the spirit of homologies from algebraic topology. Petersen coloring conjecture unifies many open problems in the area in the language of morphisms that turned out to be useful in many parts of mathematics.
Keywords
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 20 (SGA0201600001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
16-19910S
Alternative language
Project name in Czech
Grafy a zobrazení -- Algebraické vlastnosti grafů
Annotation in Czech
Hlavní dvě nosná témata projektu jsou vektorové barvení a toky v grafech. První z těchto témat souvisí s užitím semidefinitního programování pro aproximaci barevnosti, cílem projektu je zkoumat další aspekty tohoto parametru, jak strukturální tak i algoritmické. . Druhé téma zahrnuje zkoumání struktury prostoru cyklů v grafech, což je lineárně-algebraická vlastnost grafu, která zachycuje mnohé jeho vlastnosti. Cyklově spojitá zobrazení zkoumají grafy v duchu homologií z algebraické topologie. Hypotéza o Petersenově barvení zachycuje velkou část otevřených problémů v této oblasti v jazyce morfismů, který se ukázal užitečný v mnoha oblastech matematiky.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
BA - General mathematics
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
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The main project outcomes are new results in algorithmic graph theory, especially in the areas of nowhere-zero graph flows and graph colorings. The achieved results were published in high-quality journals, the main research objectives were successfully accomplished.
Solution timeline
Realization period - beginning
Jan 1, 2016
Realization period - end
Dec 31, 2018
Project status
U - Finished project
Latest support payment
Apr 26, 2018
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
CEP19-GA0-GA-U/01:1
Data delivery date
Jun 12, 2019
Finance
Total approved costs
3,222 thou. CZK
Public financial support
2,604 thou. CZK
Other public sources
618 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
3 222 CZK thou.
Public support
2 604 CZK thou.
80%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2016 - 31. 12. 2018