Contracting to a Longest Path in H-Free Graphs

We consider the problem of determining if a graph can be modified to a path by a small number of graph operations from some specified set S. If S only contains the edge contraction operation, we obtain the problem Path Contraction. A graph G is H-free for some graph H if G does not contain H as an induced subgraph. By combining known and new techniques we determine the complexity of Path Contraction on H-free graphs for every graph H. We do this by exploiting a relation to the problem of finding disjoint connected subgraphs, each containing some prescribed set of vertices. We compare our classification with the classifications for Hamilton Path, Long Path and Longest Induced Path on H-free graphs. The first two classifications are still incomplete and we will discuss relevant open problems. This is joint work with Walter Kern.

Join Zoom Meeting HERE!

For more info visit our YouTube Channel.