• česky
  • english
Přejít na obsah | Přejít na menu

Informační systém výzkumu, experimentálního vývoje a inovací
výzkum, vývoj a inovace podporované z veřejných prostředků ČR

    • Poskytovatelé podpory ve výzkumu, vývoji a inovacích (RPO)
    • Programy výzkumu, vývoje a inovací (RPG)
    • Subjekty ve výzkumu, vývoji a inovacích (RPR)
  • Veřejné soutěže ve výzkumu, vývoji a inovacích (VES)
  • Projekty výzkumu, vývoje a inovací (CEP)
  • Výzkumné záměry (CEZ)
  • Výsledky výzkumu, vývoje a inovací (RIV)

RIV/00216208:11320/08:00100594 - Graph colouring with no large monochromatic components (2008)

Údaje o výsledku
Identifikační kódRIV/00216208:11320/08:00100594
Název v původním jazyceGraph colouring with no large monochromatic components
Název českyObarvení grafů bez velkých jednobarevných komponent
DruhJ - Článek v odborném periodiku
Jazykeng - angličtina
OborBA - Obecná matematika
Rok uplatnění2008
Kód důvěrnosti údajůS - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
Počet výskytů výsledku1
Tvůrci výsledku
Počet tvůrců celkem4
Počet domácích tvůrců1
TvůrceLinial Nathan (státní příslušnost: CZ - Česká republika)
TvůrceMatoušek Jiří (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku)
TvůrceSheffet Or (státní příslušnost: CZ - Česká republika)
TvůrceTardos Gábor (státní příslušnost: CZ - Česká republika)
Údaje blíže specifikující výsledek
Popis v původním jazyceFor a graph G, we define mcc(t,G) as the smallest m such that there is a coloring of V(G) by t colors so that no monochromatic connected subgraph of G has more than m vertices. For various graph classes we investitgate the maximum of mcc(2,G) over all n-vertex graphs in the class. In particular, for the class of all planar graphs this maximum is of order n to 2/3.
Popis českyPro graf G definujeme mcc(t,G) jako nejmenší číslo m takové, že existuje obarvení vrcholů G pomocí t barev takové, že žádný souvislý jednobarevný podgraf nemá víc než m vrcholů. Pro různé třídy grafů se zkoumá maximum mcc(2,G) přes všechny n=vrcholové grafy z příslušné třídy. Například se dokazuje, že pro rovinné grafy je toto maximum řádu n na 2/3.
Klíčová slovaGraph; colouring; large; monochromatic; components
Kód UT ISI000258173600009
Název periodkaCombinatorics Probability and Computing
ISSN0963-5483
Svazek periodika17
Číslo periodika v rámci uvedeného svazku4
Stát vydavatele periodikaGB - Spojené království Velké Británie a Severního Irska
Počet stran výsledku13
Údaje o tomto záznamu o výsledku
PředkladatelUniverzita Karlova v Praze / Matematicko-fyzikální fakulta
DodavatelMSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT)
Rok sběru2009
Systémové označení dodávky datRIV09-MSM-11320___/01:1
Datum dodání2.7.2009
SpecifikaceRIV/00216208:11320/08:00100594!RIV09-MSM-11320___
Kontrolní kód[C5E5115E12FC]
Jiný výskyt tohoto výsledku se v RIV nenachází
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
Projekt1M0545 - Institut Teoretické Informatiky (2005-2011, MSM/1M)
Výzkumný záměrMSM0021620838 - Moderní metody, struktury a systémy informatiky (2005-2011, MSM)
Tuto aplikaci pro Radu pro výzkum, vývoj a inovace provozuje Výpočetní a informační centrum Českého vysokého učení technického v Praze. Vyvíjí InfoScience Praha s.r.o.. Verze aplikace 1.6.15. Datové schéma ISVAV_WEB5_00318. Podpora uživatelů na e-mailové adrese podpora (zavináč) isvav (tečka) cz nebo telefonním čísle 224 234 797 (v pracovních dnech 8-16 hod.).