Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917900958302208 |
|---|---|
| author | Bourneuf, Romain Masaříková, Jana Nadara, Wojciech Pilipczuk, Marcin |
| author_facet | Bourneuf, Romain Masaříková, Jana Nadara, Wojciech Pilipczuk, Marcin |
| contents | For a fixed integer $t \geq 1$, a ($t$-)long claw, denoted $S_{t,t,t}$, is the unique tree with three leaves, each at distance exactly $t$ from the vertex of degree three. Majewski et al. [ICALP 2022, ACM ToCT 2024] proved an analog of the Gyárfás' path argument for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, one can delete neighborhoods of $\mathcal{O}(\log n)$ vertices so that the remainder admits an extended strip decomposition (an appropriate generalization of partition into connected components) into particles of multiplicatively smaller size. This statement has proven to be very useful in designing quasi-polynomial time algorithms for Maximum Weight Independent Set and related problems in $S_{t,t,t}$-free graphs.
In this work, we refine the argument of Majewski et al. and show that a constant number of neighborhoods suffice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13907 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument Bourneuf, Romain Masaříková, Jana Nadara, Wojciech Pilipczuk, Marcin Combinatorics Discrete Mathematics Data Structures and Algorithms G.2.2 For a fixed integer $t \geq 1$, a ($t$-)long claw, denoted $S_{t,t,t}$, is the unique tree with three leaves, each at distance exactly $t$ from the vertex of degree three. Majewski et al. [ICALP 2022, ACM ToCT 2024] proved an analog of the Gyárfás' path argument for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, one can delete neighborhoods of $\mathcal{O}(\log n)$ vertices so that the remainder admits an extended strip decomposition (an appropriate generalization of partition into connected components) into particles of multiplicatively smaller size. This statement has proven to be very useful in designing quasi-polynomial time algorithms for Maximum Weight Independent Set and related problems in $S_{t,t,t}$-free graphs. In this work, we refine the argument of Majewski et al. and show that a constant number of neighborhoods suffice. |
| title | Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms G.2.2 |
| url | https://arxiv.org/abs/2501.13907 |