Finding Large Subgraphs
Department of Applied Mathematics
Illinois Institute of Technology
The maximum subgraph problem for a fixed graph property P asks: Given a graph, find a subgraph satisfying property P that has the maximum number of edges. Similarly, we can talk about maximum induced subgraph problem. This property can be planarity, acyclicity, bipartiteness, etc.
We will discuss some old and new problems of this flavor with special emphasis on properties defined in terms of forbidden minors. In particular, we will describe some new results on the maximum K_4 - minor-free subgraph problem (joint work with Calinescu and Fernandes).