MUIC Math

Mathematics at MUIC

User Tools

Site Tools


seminar:cl_excluded_minor

Differences

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

Link to this comparison view

seminar:cl_excluded_minor [2017/03/13 09:07] (current)
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}}
Last modified: 2017/03/13 09:07