Ramsey numbers of ordered graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10313908" target="_blank" >RIV/00216208:11320/15:10313908 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S1571065315001055" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1571065315001055</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.endm.2015.06.059" target="_blank" >10.1016/j.endm.2015.06.059</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Ramsey numbers of ordered graphs

Popis výsledku v původním jazyce

An ordered graph is a graph together with a total ordering of its vertices. We study ordered Ramsey numbers, the analogue of Ramsey numbers for ordered graphs. In contrast with the case of unordered graphs, we show that there are ordered matchings whoseordered Ramsey numbers are super-polynomial in the number of vertices. We also prove that ordered Ramsey numbers are polynomial in the number of vertices of the given ordered graph G if G has constant degeneracy and constant interval chromatic number orif G has constant bandwidth. The latter result answers positively a question of Conlon, Fox, Lee, and Sudakov. For a few special classes of ordered graphs, we give asymptotically tight bounds for their ordered Ramsey numbers. For so-called monotone cycles we compute their ordered Ramsey numbers exactly.

Název v anglickém jazyce

Ramsey numbers of ordered graphs

Popis výsledku anglicky

An ordered graph is a graph together with a total ordering of its vertices. We study ordered Ramsey numbers, the analogue of Ramsey numbers for ordered graphs. In contrast with the case of unordered graphs, we show that there are ordered matchings whoseordered Ramsey numbers are super-polynomial in the number of vertices. We also prove that ordered Ramsey numbers are polynomial in the number of vertices of the given ordered graph G if G has constant degeneracy and constant interval chromatic number orif G has constant bandwidth. The latter result answers positively a question of Conlon, Fox, Lee, and Sudakov. For a few special classes of ordered graphs, we give asymptotically tight bounds for their ordered Ramsey numbers. For so-called monotone cycles we compute their ordered Ramsey numbers exactly.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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ů

Název periodika

Electronic Notes in Discrete Mathematics

ISSN

1571-0653

e-ISSN

—

Svazek periodika

49

Číslo periodika v rámci svazku

November 2015

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

6

Strana od-do

419-424

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-84947731447