Rainbow connection and cycles in graphs
Project goals
In the project, we will consider two important problems in the field of Graph Theory: (i) rainbow colouring of graphs, especially computation of (or at least bounds for) the rainbow connection number rc(G) of a given graph G ? the problem has an interesting application for the secure transfer of classified information between agencies in communication networks; (ii) computation of (or at least bounds for the size of) a largest subgraph with prescribed properties ? cycle, path, trestle (a spanning 2-connected subgraph of bounded degree) etc. ? knowledge about such subgraphs has major importance on the structure of a given graph and its other graph properties.
Keywords
edge colouringrainbow connectionlongest cyclehamiltonicitytrestle
Public support
Provider
Ministry of Education, Youth and Sports
Programme
—
Call for proposals
FP6-2004-Mobility-12
Main participants
—
Contest type
RP - Co-financing of EC programme
Contract ID
MSMT-8032/2013-311
Alternative language
Project name in Czech
Duhová souvislost a cykly v grafech
Annotation in Czech
V projektu se budeme zabývat dvěma důležitými problémy teorie grafů: (i) duhové barvení grafů, zejména určení (či odhady) duhového čísla souvislosti rc(G) daného grafu G ? problém má aplikace pro bezpečný přenos informací mezi agenturami v komunikačníchsítích; (ii) nalezení (či odhady velikosti) největšího podgrafu daných vlastností ? kružnice, cesty, trestle (2-souvislého faktoru s omezeným maximálním stupněm) atd. v daném (konečném) grafu ? znalost těchto podgrafů má významnou roli pro strukturu daného grafu a jeho další grafové vlastnosti.
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
This project is being realized in the framework of the MOBILITY Activity that aims primarily on establishing and strenghtening ties with foreign research institutions. The control of particular outputs is not implemented by the evalution committee, but the correctness of allocated finances and the adequacy of their use are checked.
Solution timeline
Realization period - beginning
Jan 1, 2013
Realization period - end
Dec 31, 2014
Project status
U - Finished project
Latest support payment
Feb 4, 2014
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
CEP15-MSM-7A-U/01:1
Data delivery date
Jul 2, 2015
Finance
Total approved costs
82 thou. CZK
Public financial support
82 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
82 CZK thou.
Public support
82 CZK thou.
100%
Provider
Ministry of Education, Youth and Sports
CEP
BA - General mathematics
Solution period
01. 01. 2013 - 31. 12. 2014