The Ohio State University

VIGRE at The Ohio State University
--- Invitation to Research ---

Department of Mathematics

Invitation to Graph Theory [Spring 2006]

Neil Robertson

There will be two lectures in this series. The first will present several problems which can be formulated with elementary notation and are at three levels, recreational, course exercises and fundamentally challenging. Some simple basic notation and theorems will be introduced in this context. An example of such a theorem states that the axiom of choice for families of nonempty subsets is equivalent to existence of spanning trees in all connected graphs. The second lecture will complete this material and explore some chromatic number problems related to contraction minors (topological graph theory) and vertex-deleted subgraphs (optimization/extremal graph theory).