Induced Ramsey Number for a Star Versus a Fixed Graph
Artykuł w czasopiśmie
MNiSW
100
Lista 2021
| Status: | |
| Autorzy: | Axenovich Maria, Gorgol Izolda |
| Dyscypliny: | |
| Aby zobaczyć szczegóły należy się zalogować. | |
| Rok wydania: | 2021 |
| Wersja dokumentu: | Drukowana | Elektroniczna |
| Język: | angielski |
| Numer czasopisma: | 1 |
| Wolumen/Tom: | 28 |
| Numer artykułu: | P1.55 |
| Strony: | 1 - 13 |
| Web of Science® Times Cited: | 0 |
| Scopus® Cytowania: | 0 |
| Bazy: | Web of Science | Scopus | MathSciNet | ScienceDirect |
| Efekt badań statutowych | NIE |
| Materiał konferencyjny: | NIE |
| Publikacja OA: | TAK |
| Licencja: | |
| Sposób udostępnienia: | Otwarte czasopismo |
| Wersja tekstu: | Ostateczna wersja opublikowana |
| Czas opublikowania: | W momencie opublikowania |
| Data opublikowania w OA: | 26 marca 2021 |
| Abstrakty: | angielski |
| We write Find⟶(H,G) for graphs F,G, and H, if for any coloring of the edges of F in red and blue, there is either a red induced copy of H or a blue induced copy of G. For graphs G and H, let IR(H,G) be the smallest number of vertices in a graph F such that Find⟶(H,G). In this note we consider the case when G is a star on n edges, for large n and H is a fixed graph. We prove that (χ(H)−1)n≤IR(H,K1,n)≤(χ(H)−1)2n+ϵn, for any ϵ>0, sufficiently large n, and χ(H) denoting the chromatic number of H. The lower bound is asymptotically tight for any fixed bipartite H. The upper bound is attained up to a constant factor, for example when H is a clique. |
