Graph coloring and structure
Project goals
The project is focused at the chromatic and structural properties of graphs. Its goal is to obtain substantial new results allowing for a more detailed understanding of problems related to graph coloring and structure. Particular topics within the scope of the project include the fractional coloring of graphs with bounded clique number, the coloring of graphs not containing a subdivision or an immersion of a given graph, nowhere-zero flows and group connectivity, or questions concerning the structure of cycles in graphs, such as shortest cycle covers or structural problems of hamiltonian type. The topics are described in more detail in the project proposal. Potential applications of the results re related, e.g., to the frequency assignment problem in the development of mobile networks.
Keywords
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 18 (SGA0201400001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Západočeská univerzita v Plzni / Fakulta aplikovaných vědContest type
VS - Public tender
Contract ID
14-19503S
Alternative language
Project name in Czech
Barevnost a struktura grafů
Annotation in Czech
Projekt je zaměřen na chromatické a strukturální vlastnosti grafů. Cílem projektu je získání podstatných nových poznatků, umožňujících detailnější pochopení problematiky barevnosti a struktury grafů. Konkrétní témata, na která bude projekt zaměřen, zahrnují frakcionální barevnost grafů s omezenou klikovostí, barevnost grafů neobsahujících podrozdělení nebo imerzi daného grafu, nenulové toky a grupovou souvislost, nebo otázky související se strukturou cyklů v grafech: nejkratší pokrytí kružnicemi a strukturální problémy hamiltonovského typu. Přesnější formulace otázek jsou uvedeny v návrhu projektu. Potenciální aplikace výsledků se vztahují mj. k problému přiřazování frekvencí v oblasti mobilních sítí.
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 results deal with graph coloring, non-zero flows in graphs, structure of cycles and related areas. The works focus on essential problems in the area, including brand new approaches, and they greatly contribute to the knowledge in the graph theory. Both number and quality of publications and presentations on international forums are impressive. The involvement of students is great too.
Solution timeline
Realization period - beginning
Jan 1, 2014
Realization period - end
Apr 23, 2018
Project status
U - Finished project
Latest support payment
May 6, 2016
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,936 thou. CZK
Public financial support
3,936 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
3 936 CZK thou.
Public support
3 936 CZK thou.
0%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 2014 - 23. 04. 2018