Splits with forbidden subgraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912217481347072 |
|---|---|
| author | Axenovich, Maria Martin, Ryan R. |
| author_facet | Axenovich, Maria Martin, Ryan R. |
| contents | In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be "split" such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let
$$ f(n,H) = \min \{k \in \mathbb N : \mbox{there is an $(n,k)$-graph $G$ such that $H\not\subseteq G$}\} . $$
Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Turán exponent, i.e., ${\rm ex}(n, H) = Θ(n^r)$ for some $r$, we show that $Ω(n^{2/r -1}) = f(n, H) = O (n^{2/r-1} \log ^{1/r} n)$. We extend this result to all bipartite graphs for which an upper and a lower Turán exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =Θ(n^{1/3})$ for any fixed $t$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_14466 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Splits with forbidden subgraphs Axenovich, Maria Martin, Ryan R. Combinatorics 05C35, 05D40 In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be "split" such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let $$ f(n,H) = \min \{k \in \mathbb N : \mbox{there is an $(n,k)$-graph $G$ such that $H\not\subseteq G$}\} . $$ Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Turán exponent, i.e., ${\rm ex}(n, H) = Θ(n^r)$ for some $r$, we show that $Ω(n^{2/r -1}) = f(n, H) = O (n^{2/r-1} \log ^{1/r} n)$. We extend this result to all bipartite graphs for which an upper and a lower Turán exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =Θ(n^{1/3})$ for any fixed $t$. |
| title | Splits with forbidden subgraphs |
| topic | Combinatorics 05C35, 05D40 |
| url | https://arxiv.org/abs/2006.14466 |