Title: Graph classes: interrelations, structure, and algorithmic issues Abstract: In many applications of graph theory, it is of crucial importance to be able to efficiently detect various kinds of substructures in graphs (matchings, cliques, stable sets, dominating sets, etc.). Often, the respective computational problems turn out to be intractable in general. A possible approach in this case is to identify restrictions on input instances under which the problems can still be solved efficiently. Such restrictions can be systematically described and studied using the notion of graph classes, that is, sets of graphs closed under isomorphism. Perhaps the best known example of a graph class is the class of perfect graphs. Four decades after Berge posed the so-called Strong Perfect Graph Conjecture regarding the characterization of perfect graphs by means of their forbidden induced subgraphs, the conjecture was proved by Chudnovsky, Robertson, Seymour and Thomas in 2002 and became known as the Strong Perfect Graph Theorem. A lot of research has also been devoted to the study of numerous subclasses of perfect graphs such as chordal graphs, interval graphs, split graphs, bipartite graphs, comparability graphs, etc. In the first part of the talk, we will give a brief overview of some of the most important classes of perfect graphs, their interrelations, characterizations and algorithmic properties. While the above classes are typically defined in purely combinatorial terms, numerical characterizations of graph classes have also played an important role in (pure and algorithmic) graph theory. They will be the subject of the second part of the talk. A possible way to define a graph class numerically is via the following generic framework: Fix a property P, meaningful for vertex or edge subsets of a graph (for example, P can be a matching, a clique, a stable set, a dominating set, a total dominating set, etc.). Given a graph G, does G admit positive integer weights on its vertices (edges) and a set T such that P(S) holds if and only if the sum of the weights of elements of S belongs to T? For a proper choice of property P and a restriction on the set T, several graph classes can be defined this way, for example, threshold graphs, domishold graphs and equistable graphs. After giving an overview of these classes and their properties, we will discuss the advantages and limitations of the above framework. We will conclude the talk with an interesting family of numerically defined graphs: circulant graphs. For all graph classes discussed throughout the talk, we will address known results regarding the complexity of their recognition and of four classical graph optimization problems: COLORABILITY, CLIQUE, INDEPENDENT SET and DOMINATING SET. Several open questions will be presented.
******** CSS e script comuni siti DOL - frase 9957 ********p>