Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.19915 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |