Ramseyovské aspekty barvení grafů
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 21 (SGA0201700001)
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta<br>Západočeská univerzita v Plzni / Fakulta aplikovaných věd
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
17-04611S
Alternativní jazyk
Název projektu anglicky
Ramsey-like aspects of graph coloring
Anotace anglicky
Ramsey theory studies conditions guaranteeing existence of large well-structured subobjects in a given object. One of the approaches to bound the size of such a subobject is to show that the object can be partitioned into a small number of well-structured subobjects; one of them necessarily has to be large. In other words, we are looking for a coloring by a small number of colors, each of them inducing a subobject with given properties. This gives a natural connection between graph coloring and Ramsey theory. The connection goes both ways - many results in graph coloring are inspired or use tools from Ramsey theory. We will study problems on the boundary of these two areas, for example, size of independent sets in sparse graph classes (in relation to their fractional chromatic number), existence of subgraphs of prescribed girth and chromatic number in graphs with large chromatic number, and Erdős-Hajnal conjecture concerning the size of homogeneous subsets in hereditary classes of graphs.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)
10101 - Pure mathematics
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Výsledky projektu jsou odpovídající. Bylo publikováno 12 článků v rozumných časopisech.
Termíny řešení
Zahájení řešení
1. 1. 2017
Ukončení řešení
31. 12. 2019
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
22. 5. 2019
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP20-GA0-GA-U/02:1
Datum dodání záznamu
23. 7. 2020
Finance
Celkové uznané náklady
4 923 tis. Kč
Výše podpory ze státního rozpočtu
3 737 tis. Kč
Ostatní veřejné zdroje financování
1 186 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč