Graph Partitions and their Applications
Project goals
Many of the notions in graph theory, in particular, colorings, flows and matchings turn out to be partitions of a graph with particular properties. This observation is actually reflected in the relationships between these objects; edge colorings are often best viewed as decompositions into matchings, and conversely, some of the methods originally developed for graph colorings are useful in the study of matchings. The project aims to investigate these notions, especially for structured graphs arising from idealizations of practical problems (e.g., planar graphs, hypercubes).
Keywords
Public support
Provider
Ministry of Education, Youth and Sports
Programme
KONTAKT
Call for proposals
—
Main participants
—
Contest type
M2 - International cooperation
Contract ID
5362/2010-32
Alternative language
Project name in Czech
Rozklady grafů a jejich aplikace
Annotation in Czech
Mnoho z konceptů studovaných v teorii grafů lze chápat jako rozklad grafu na části splňující nějaké podmínky, zmiňme například barvení, toky a párování. Toto pozorování se odráží ve vztazích mezi těmito koncepty: hranové barvení je často studováno jako rozklad na párování, a naopak metody původně navržené pro studium barvení lze často použít i pro problémy spojené s existencí párování. Cílem projektu je studovat tyto vztahy a koncepty, zejména pro strukturované třídy grafů motivované praktickými problémy (rovinné grafy, hyperkrychle).
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
We significantly enhanced the knowledge regarding the precoloring extension problems, regarding the fractional coloring in general graphs and 5-list-coloring in planar graphs. We also studied highly-symmetrical graphs with applications in parallel computation.
Solution timeline
Realization period - beginning
Jan 1, 2010
Realization period - end
Dec 31, 2011
Project status
U - Finished project
Latest support payment
Mar 4, 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-MSM-ME-U/01:1
Data delivery date
Jul 12, 2012
Finance
Total approved costs
112 thou. CZK
Public financial support
112 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
112 CZK thou.
Public support
112 CZK thou.
100%
Provider
Ministry of Education, Youth and Sports
CEP
BA - General mathematics
Solution period
01. 01. 2010 - 31. 12. 2011