{"ID":2844954,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.05285","arxiv_id":"2511.05285","title":"Awesome graph parameters","abstract":"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.","short_abstract":"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 seco...","url_abs":"https://arxiv.org/abs/2511.05285","url_pdf":"https://arxiv.org/pdf/2511.05285v2","authors":"[\"Kenny Bešter Štorgel\",\"Clément Dallard\",\"Vadim Lozin\",\"Martin Milanič\",\"Viktor Zamaraev\"]","published":"2025-11-07T14:48:30Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}