MUIC Math

Mathematics at MUIC

Internal

seminar:cl_excluded_minor

Excluded Minor Theorems for Graphs

Chanun Lewchalermvongs
Department of Mathematics, Faculty of Science, Mahidol University

16:00 Wednesday 15 March 2017, Room 3303, MUIC

Abstract

A graph $H$ is a minor of a graph $G$ if $H$ is obtained from $G$ by a (possibly empty) sequence of vertex deletions, edge deletions, and edge contractions (where the order of the graph operations is irrelevant). Then $G$ is called $H$-free if $H$ is not a minor of $G$. Many important problems in graph theory can be formulated in terms of $H$-free graphs. For instance, the four color theorem can be equivalently stated as: all $K_5$-free graphs are 4-colorable.

In this area, the two most famous open problems are to determine $K_6$-free and Petersen-free graphs. To solve problems involving $H$-free graphs, it is often desirable to explicitly determine all $H$-free graphs. An excluded minor theorem describes the structure of $H$-free graphs. We discuss excluded minor theorems for small graphs.