# MUIC Math

Mathematics at MUIC

### Site Tools

seminar:cl_excluded_minor

# Differences

This shows you the differences between two versions of the page.

 — seminar:cl_excluded_minor [2017/03/13 09:07] (current)pornrat created 2017/03/13 09:07 pornrat created 2017/03/13 09:07 pornrat created Line 1: Line 1: + << [[:seminar|Seminar]] + ====== Excluded Minor Theorems for Graphs ====== + ~~NOTOC~~ + + **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. + + + + + {{tag>seminar}}