# New Characterizations in Structural Graph Theory: 1-Perfectly Orientable Graphs, Graph Products, and the Price of Connectivity (Seminar DM)

New Characterizations in Structural Graph Theory: 1-Perfectly Orientable Graphs, Graph Products, and the Price of Connectivity

Tatiana Romina Hartinger

Torek, 3. januar 2017, od 10h do 12h, Plemljev seminar, Jadranska 19

Povzetek:

This is a presentation of PhD thesis topic. The PhD thesis will consist of three interrelated parts: 1-perfectly orientable graphs, graph products, and the price of connectivity. The central common theme among the three parts is the study of graph classes. In particular, we will examine three well known intersection graph classes which will play a key role in many of our results: chordal, interval, and circular arc graphs.

Following the terminology of Kammer and Tholey, we say that an orientation of a graph is 1-perfect if the out-neighborhood of every vertex induces a tournament, and that a graph is 1-perfectly orientable (1-p.o. for short) if it has a 1-perfect orientation. 1-perfectly orientable graphs are known to be polynomially recognizable, but a complete structural understanding of the class is still an open question. In the presentation we will discuss characterizations of 1-perfectly orientable graphs in various graph classes, including nontrivial product graphs for each of the four standard graph products (Cartesian, direct, strong, and lexicographic).

For a family of graphs F, an F-transversal of a graph G is a subset S in V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. We denote by t_F(G) be the minimum size of an F-transversal of G, and by ct_F(G) be the minimum size of an F-transversal of G that induces a connected graph. For a class of connected graphs, we say that the price of connectivity of F-transversals is multiplicative if, for all G in the class, ct_F(G)/t_F(G) is bounded by a constant, and additive if ct_F(G)-t_F(G) is bounded by a constant. The price of connectivity is identical if t_F(G) and ct_F(G) are always equal and unbounded if ct_F(G) cannot be bounded in terms of t_F(G). The price of connectivity will be discussed in the context of hereditary graph classes defined by a single forbidden induced subgraph.