Velké jednobarevné komponenty v 2-obarvených grafech

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00004976" target="_blank" >RIV/00216208:11320/07:00004976 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Large monochromatic components in two-colored grids
Popis výsledku v původním jazyce
(This paper is an extended abstract) We consider the d-dimensional grid with diagonals, which is the graph whose vertices are d-component vectors with components from {1,2,...,n} and edges connecting every two vertices that differ by at most 1 in every coordinate. We prove that whenever the vertices are colored by two colors, there exists a monochromatic connected subgraph with at leastt n^(d-1)-O(n^(d-2)) vertices, which is nearly tight. We also consider a similar problem for triangulated grids.
Název v anglickém jazyce
Large monochromatic components in two-colored grids
Popis výsledku anglicky
(This paper is an extended abstract) We consider the d-dimensional grid with diagonals, which is the graph whose vertices are d-component vectors with components from {1,2,...,n} and edges connecting every two vertices that differ by at most 1 in every coordinate. We prove that whenever the vertices are colored by two colors, there exists a monochromatic connected subgraph with at leastt n^(d-1)-O(n^(d-2)) vertices, which is nearly tight. We also consider a similar problem for triangulated grids.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—

Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2007
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)