Structure of planar graphs and applications to graph colorings and frequency assignment
Project goals
The project is proposed by research teams of Charles University in Prague, University of West Bohemia in Pilsen and University of Ljubljana. The aim of the project is investigation of structure of planar graphs with application in the channel assignmentproblem. The main goals of the project are: 1. study of structural properties of planar graphs, in particular, establishing the existence of various types of subgraphs, 2. graph theory models for the channel assignment problem, in particular, efficient and optimal solutions of such problems, 3. fostering mutual cooperation in the area of discrete mathematics, and 4. active involvement of undergraduate and graduate students in research as a part of their educational process. We expect the obtained results to appear in well-established international journals such as SIAM Journal on Discrete Mathematics, Discrete Applied Mathematics etc. Based on the level of approved support of the project, it can be expected that 6-8 or
Keywords
graph theorygraph coloringgraph labellingchannel assignment problemtopological graph theoryplanar graphs
Public support
Provider
Ministry of Education, Youth and Sports
Programme
KONTAKT
Call for proposals
—
Main participants
—
Contest type
M2 - International cooperation
Contract ID
1484/2009-32
Alternative language
Project name in Czech
Struktura rovinných grafů s použitím v problémech barevnosti grafů a přidělování frekvencí
Annotation in Czech
Projekt navrhovaný řešitelskými týmy z Univerzity Karlovy v Praze, Západočeské univerzity v Plzni a Univerzity v Ljubljani si klade za cíl studium struktury rovinných grafů s příhlednutím k aplikací v oblasti přidělování frekvencí. Hlavní cíle projekte jsou následující: 1. studium strukturálních vlastností rovinných grafů, zejména existence speciálních podgrafů v těchto grafech 2. modely teorie grafů pro problém přidělování frekvencí, zejména efektivní a optimální řešení těchto problémů, 3. prohloubenívzájemné spolupráce v oblasti diskrétní matematiky, a 4. aktivní zapojení studentů pregraduálního a postgraduálního studia do výzkumu jako součást jejich studijních plánů, např. při práci na diplomové či doktorské práci. Očekáváme, že dosažené výsledky budou publikovány v zavedených mezinárodních časopisech, např. SIAM Journal on Discrete Mathematics nebo Discrete Applied Mathematics. Na zakládě předpokládané podpory schválené pro tento projekt je reálné očekávat připravení
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
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
We provided new structural results on planar graphs, e.g., with relation to the frequency assignment in wireless networks or to structure of fullerene molecules. The obtained results are contained in 14 original research papers.
Solution timeline
Realization period - beginning
Jul 1, 2008
Realization period - end
Dec 31, 2009
Project status
U - Finished project
Latest support payment
Mar 9, 2009
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
CEP10-MSM-ME-U/01:1
Data delivery date
Jun 30, 2010
Finance
Total approved costs
160 thou. CZK
Public financial support
160 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
160 CZK thou.
Public support
160 CZK thou.
100%
Provider
Ministry of Education, Youth and Sports
CEP
BA - General mathematics
Solution period
01. 07. 2008 - 31. 12. 2009