On graphs with forbidden induced subgraphs - editing and structure

The study of graphs with forbidden local substructures is in the heart of extremal graph theory.

Two types of such forbidden substructures are fixed subgraphs and fixed induced subgraphs. Here, a subgraph is a graph obtained from a given graph by deleting vertices and edges, and an induced subgraph is a graph obtained from a given graph by deleting only vertices. I.e., the induced subgraphs inherit all the structure - edges and non-edges of a given graph.

The structure of graphs without a fixed subgraph has been studied extensively for the last sixty years. Not many results are known about graphs without forbidden induced subgraphs. However, since any hereditary property of graphs can be characterized in terms of forbidden induced subgraphs, the graphs without given induced subgraphs are of fundamental importance.

In this talk, among others, I will discuss a problem of avoiding fixed induced subgraphs in a given graph via edge deletions and edge additions, so-called graph editing. I will introduce a notion of an edit distance and show our bounds and asymptotically tight results in terms of the binary chromatic number. I will also bring up some applications of our results such as pattern avoidance in matrices and comparison analysis of evolutionary trees.