Course Page

Graph Theory

Course Number:

47835


Faculty

Egon Balas, eb17@andrew.cmu.edu


Program

PHD


Concentrations

Operations Research or Statistics


Course Description

This is the first part of a full-semester course on algorithmic graph theory. We review the basic concepts and central results of graph theory. Representations of graphs. Subgraphs, paths, cycles. Connectivity. Bipartite graphs. Trees. Euler tours and Hamilton cycles. Independent sets and cliques. Graph coloring. Planarity. Packing and covering. Perfect graphs. Chordal graphs.

Format

Lecture: 100min/wk and Recitation: 50min/wk


Pre-requisites

None