Characterization of sparse monotone graph classes with bounded domination-to-2-independence ratio
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918298927497216 |
|---|---|
| author | Bonamy, Marthe Dvořák, Zdeněk Michel, Lukas Mikšaník, David |
| author_facet | Bonamy, Marthe Dvořák, Zdeněk Michel, Lukas Mikšaník, David |
| contents | We give an exact characterization of monotone graph classes C with bounded average degree that satisfy the following property: The domination number of every graph from C is bounded by a linear function of its 2-independence number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15082 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Characterization of sparse monotone graph classes with bounded domination-to-2-independence ratio Bonamy, Marthe Dvořák, Zdeněk Michel, Lukas Mikšaník, David Combinatorics 05C69 We give an exact characterization of monotone graph classes C with bounded average degree that satisfy the following property: The domination number of every graph from C is bounded by a linear function of its 2-independence number. |
| title | Characterization of sparse monotone graph classes with bounded domination-to-2-independence ratio |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2601.15082 |