Lectio Magistralis prof. Martin Milanic

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.