- Tytuł:
- A Note on Lower Bounds for Induced Ramsey Numbers
- Autorzy:
- Gorgol, Izolda
- Powiązania:
- https://bibliotekanauki.pl/articles/31343354.pdf
- Data publikacji:
- 2019-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
- induced Ramsey number
- Opis:
- We say that a graph $F$ strongly arrows a pair of graphs $(G,H)$ and write \( F \xrightarrow{ind} (G,H) \) if any 2-coloring of its edges with red and blue leads to either a red $G$ or a blue $H$ appearing as induced subgraphs of $F$. The induced Ramsey number, $ IR(G,H) $ is defined as \( \min \{ |V (F)| : F \xrightarrow{ind} \) $ (G,H) \} $. We will consider two aspects of induced Ramsey numbers. Firstly we will show that the lower bound of the induced Ramsey number for a connected graph $G$ with independence number $ \alpha $ and a graph $H$ with clique number $ \omega $ is roughly \( \tfrac{ \omega^2 \alpha } { 2 } \). This bound is sharp. Moreover we will also consider the case when $G$ is not connected providing also a sharp lower bound which is linear in both parameters.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 647-654
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł