Sparse Partitions of Graphs with Bounded Clique Number
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909409278427136 |
|---|---|
| author | Girão, António Insley, Toby |
| author_facet | Girão, António Insley, Toby |
| contents | We prove that for each integer $r\geq 2$, there exists a constant $C_r>0$ with the following property: for any $0<\varepsilon \leq 1/2$ and any graph $G$ with clique number at most $r,$ there is a partition of $V(G)$ into at most $(1/\varepsilon)^{C_r}$ sets $S_1, \dots, S_t,$ such that $G[S_i]$ has maximum degree at most $\varepsilon |S_i|$ for each $1 \leq i \leq t.$ This answers a question of Fox, Nguyen, Scott and Seymour, who proved a similar result for graphs with no induced $P_4.$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19915 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparse Partitions of Graphs with Bounded Clique Number Girão, António Insley, Toby Combinatorics We prove that for each integer $r\geq 2$, there exists a constant $C_r>0$ with the following property: for any $0<\varepsilon \leq 1/2$ and any graph $G$ with clique number at most $r,$ there is a partition of $V(G)$ into at most $(1/\varepsilon)^{C_r}$ sets $S_1, \dots, S_t,$ such that $G[S_i]$ has maximum degree at most $\varepsilon |S_i|$ for each $1 \leq i \leq t.$ This answers a question of Fox, Nguyen, Scott and Seymour, who proved a similar result for graphs with no induced $P_4.$ |
| title | Sparse Partitions of Graphs with Bounded Clique Number |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.19915 |