Awesome graph parameters

Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin, Martin Milanič, Viktor Zamaraev · 2025

Read Awesome graph parameters by Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin, Martin Milanič, Viktor Zamaraev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-05285.txt.

Introduction

Kenny Bešter Štorgel and co-authors study graph parameters that blend two classic counts: the largest set of unlinked nodes and the largest fully linked set. One research line builds variants of known parameters based on the first count.

A second line studies graph classes where a parameter is capped by a function of the clique count. Their work sits on the edge of both lines, with a Ramsey-style claim as a bridge. Results of this kind sort which graph traits must grow together, a theme that runs through structural graph theory.

Catalog record

CREATORKenny Bešter Štorgel, Clément Dallard, Vadim Lozin, Martin Milanič, Viktor Zamaraev
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-05285

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Awesome graph parameters Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin, Martin Milanič, Viktor Zamaraev Abstract For a graph G G , we denote by α ⁡ ( G ) \alpha(G) the size of a maximum independent set and by ω ⁡ ( G ) \omega(G) the size of a maximum clique in G G . Our paper lies on the edge of two lines of research, related to α \alpha and ω \omega , respectively. One of them studies α \alpha -variants of graph parameters, such as α \alpha -treewidth or α \alpha -degeneracy. The second line deals with graph classes where some parameters are bounded by a function of ω ⁡ ( G ) \omega(G) . A famous example of this type is the family of χ \chi -bounded classes, where the chromatic number χ ⁡ ( G ) \chi(G) is bounded by a function of ω ⁡ ( G ) \omega(G) . A Ramsey-type argument implies that if the α \alpha -variant of a graph parameter ρ \rho is bounded by a constant in a class 𝒢 \mathcal{G} , then ρ \rho is bounded by a function of ω \omega in 𝒢 \mathcal{G} . If the reverse implication also holds, we say that ρ \rho is awesome . Otherwise, we say that ρ \rho 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. 1 Introduction Graph parameters play a central role in structural and algorithmic graph theory, capturing key combinatorial properties of graphs. Often, a desirable algorithmic or structural property is established by identifying a suitable graph parameter and showing that the target behaviour follows from its boundedness. For example, bounded degeneracy ensures that every subgraph has a low-degree vertex, enabling compact graph representations [ 65 ] ; bounded treewidth yields efficient algorithms for problems expressible in monadic second-order logic that are NP -hard in general [ 24 ] . A potential limitation of this approach is that boundedness of a graph parameter can substantially restrict graph structure: for instance, graphs of bounded treewidth are necessarily sparse, so boundedness of treewidth does not capture dense graphs. This motivates the study of relaxations or generalisations of boundedness of graph parameters that retain useful structural properties or algorithmic tractability while encompassing richer classes. The present paper is on the edge of two such lines of research. The first concerns clique-bounded parameters , where the value of a parameter is bounded as a function of the clique number \omega . A central example is the theory of \chi -bounded classes—hereditary classes in which the chromatic number \chi(G) is bounded by a function of \omega(G) —which emerged as a generalisation of perfect graphs [ 40 ] , and has been the subject of extensive study (see, e.g., [ 63 ] ). A more recent example is the family of (\mathrm{tw},\omega) -bounded classes, where the treewidth is bounded by a function of the clique number; such classes are known to have useful algorithmic applications (see [ 29 , 14 ] ). The second line focuses on independence variants of parameters. The independence variant of a parameter \rho , denoted \alpha - \rho , is obtained by relaxing the size constraint in the definition of \rho to one on the independence number. These variants are motivated in part by algorithmic considerations: for example, bounded \alpha -treewidth—a parameter introduced independently by Yolov [ 67 ] and by Dallard, Milanič, and Štorgel (under the name tree-independence number [ 30 , 31 ] )—still guarantees polynomial-time solvability of the Maximum Weight Independent Set problem (and many others, see [ 27 , 67 , 52 , 30 , 15 ] ), while capturing significantly larger graph classes than bounded treewidth. Another example of this type is the following independence variant of degeneracy: the \alpha -degeneracy of a graph G is the minimum k such that every induced subgraph of G has a vertex whose neighbourhood has independence number at most k . This parameter was studied under the name inductive independence number by Ye and Borodin [ 66 ] , from both structural and algorithmic points of view. A simple Ramsey-type argument (see Section 3.4 ) shows that bounded \alpha - \rho always implies that \rho is clique-bounded. This observation allows properties implied by clique-boundedness of \rho to be transferred automatically to classes with bounded \alpha - \rho . It is natural to ask whether the converse holds: Does clique-boundedness of \rho always imply boundedness of \alpha - \rho ? Such an implication is not always straightforward. For example, motivated by the complexity of the Maximum Weight Independent Set problem, it was conjectured that clique-boundedness of treewidth implies boundedness of \alpha -treewidth [ 31 ] (see also [ 29 ] ); this remained open for some time before being recently refuted by Chudnovsky and Trotignon [ 23 ] . Nevertheless, the question of whether Maximum Weight Independent Set problem admits a polynomial-time algorithm in any hereditary graph class with clique-bounded treewidth, raised by Dallard, Milanič, and Štorgel in [ 29 , 31 ] , remains open. Motivated by the example of treewidth, in this paper, we formalise the notions of clique-boundedness and independence variants of graph parameters, and investigate when the two notions coincide. Specifically, a graph parameter \rho is said to be awesome if clique-boundedness of \rho is equivalent to boundedness of \alpha - \rho , and is awful otherwise. Formal treatment of these notions is given in Section 3 . In Section 4 , we show that treedepth and pathwidth are awful parameters. In Section 5 , we identify some parameters that are awesome, and derive structural and algorithmic consequences of awesomeness, including an infinite family of graph parameters \rho such that Maximum Weight Independent Set problem admits a polynomial-time algorithm in any hereditary graph class with clique-bounded \rho . We conclude with a discussion of further questions and open problems in Section 6 . In the next section, we introduce basic notation and main notions. 2 Preliminaries We denote by \mathbb{N} the set of all positive integers. All graphs considered in this paper are finite, simple, and undirected. Let G=(V,E) be a graph. We denote by V(G) and E(G) the vertex set and the edge set of G , respectively. For a set S\subseteq V(G) , we denote by G[S] the subgraph of G induced by S . The neighbourhood of a vertex v in G , denoted by N_{G}(v) , is the set of vertices adjacent to v in G . For a set S\subseteq V(G) , we denote N_{G}(S)=(\bigcup_{v\in S}N_{G}(v))\setminus S . When the graph G is clear from the context, we may omit the subscript and simply write N(v) and N(S) . A vertex v is universal in G if N_{G}(v)=V(G)\setminus\{v\} . The degree of v is the cardinality of the set N_{G}(v) . The maximum degree of a graph G , denoted by \Delta(G) , is the largest degree of a vertex in G . We use the standard notation K_{p,q} , K_{s} , P_{s} , and C_{s} , for the complete bipartite graph with p

Read the complete text