Department of Applied Mathematics and Statistics, Johns Hopkins University

550.770 Topics in Discrete Mathematics

Graph Classes and Representations of Graphs

This will be an overview of important classes of graphs and their properties. We will be especially interested in hereditary classes (closed under induced subgraph or other such orders) including perfect graphs, interval graphs, chordal graphs, etc. We will consider graph classes as objects of study unto themselves and (depending on student interests) algorithms for recognition (and related computational complexity results).

Students are expected to be active participants in the course and will be responsible for lecturing on specific topics.

Prerequisites

• 550.672 Graph Theory required.
• 550.671 Combinatorial Analysis highly recommended.

Textbooks

• A. Brandstadt, V. B. Le, and J. P. Spinrad, Graph Classes: A Survey, SIAM (1999).
• J. Spinrad, Efficient Graph Representations, AMS (2003)

Meetings

• Tuesdays and Thursdays, 12:30 to 1:45 in Whitehead 303 (department library).

Instructor

• Edward Scheinerman

Class Notes

• Click here for lecture notes written by students in the class.