Awesome graph parameters
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915693223477248 |
|---|---|
| author | Štorgel, Kenny Bešter Dallard, Clément Lozin, Vadim Milanič, Martin Zamaraev, Viktor |
| author_facet | Štorgel, Kenny Bešter Dallard, Clément Lozin, Vadim Milanič, Martin Zamaraev, Viktor |
| contents | For a graph $G$, we denote by $α(G)$ the size of a maximum independent set and by $ω(G)$ the size of a maximum clique in $G$. Our paper lies on the edge of two lines of research, related to $α$ and $ω$, respectively. One of them studies $α$-variants of graph parameters, such as $α$-treewidth or $α$-degeneracy. The second line deals with graph classes where some parameters are bounded by a function of $ω(G)$. A famous example of this type is the family of $χ$-bounded classes, where the chromatic number $χ(G)$ is bounded by a function of $ω(G)$.
A Ramsey-type argument implies that if the $α$-variant of a graph parameter $ρ$ is bounded by a constant in a class $\mathcal{G}$, then $ρ$ is bounded by a function of $ω$ in $\mathcal{G}$. If the reverse implication also holds, we say that $ρ$ is awesome. Otherwise, we say that $ρ$ is awful. In the present paper, we identify a number of awesome and awful graph parameters, derive some algorithmic applications of awesomeness, and propose a number of open problems related to these notions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_05285 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Awesome graph parameters Štorgel, Kenny Bešter Dallard, Clément Lozin, Vadim Milanič, Martin Zamaraev, Viktor Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75 (Primary), 05D10, 05C69, 05C65, 05C85 (Secondary) For a graph $G$, we denote by $α(G)$ the size of a maximum independent set and by $ω(G)$ the size of a maximum clique in $G$. Our paper lies on the edge of two lines of research, related to $α$ and $ω$, respectively. One of them studies $α$-variants of graph parameters, such as $α$-treewidth or $α$-degeneracy. The second line deals with graph classes where some parameters are bounded by a function of $ω(G)$. A famous example of this type is the family of $χ$-bounded classes, where the chromatic number $χ(G)$ is bounded by a function of $ω(G)$. A Ramsey-type argument implies that if the $α$-variant of a graph parameter $ρ$ is bounded by a constant in a class $\mathcal{G}$, then $ρ$ is bounded by a function of $ω$ in $\mathcal{G}$. If the reverse implication also holds, we say that $ρ$ is awesome. Otherwise, we say that $ρ$ is awful. In the present paper, we identify a number of awesome and awful graph parameters, derive some algorithmic applications of awesomeness, and propose a number of open problems related to these notions. |
| title | Awesome graph parameters |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75 (Primary), 05D10, 05C69, 05C65, 05C85 (Secondary) |
| url | https://arxiv.org/abs/2511.05285 |