2025/11/07 by Štorgel, Kenny Bešter, Dallard, Clément, Lozin, Vadim +2
#05C65 #05C69 #05C75 (Primary) #05C85 (Secondary) #05D10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2511.05285
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 G, then ρ is bounded by a function of ω in 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.