**Algorithmic Graph Theory**

** Prof. Martin
Golumbic **

**Slides and Notes of
Selected Lectures (click here)**

**Course Description:**

We present classical and more recent theory and algorithms in graph
theory, in particular, related to intersection graphs and other structured
families of graphs. Intersection graphs
are an extremely useful model for many applications in computer science, operations
research and even molecular biology, with interesting and diverse mathematical
properties.

We begin by explaining and motivating the concept, and provide
examples from the literature. The graph coloring problem on special families of
these intersection graphs will be studied, many of which admit efficient
algorithms. These techniques can be applied to scheduling classrooms or
airplanes, allocating machines or personnel to jobs, or designing circuits.
Rich mathematical problems also arise in the study of intersection graphs.

We will present a spectrum of research results, from simple to
sophisticated, which should interest both students and professors.

**Lectures will be chosen from
the following list of topics.**

Introduction to Intersection Graphs - [Go1, Mc21]

Review of Basic Graph Algorithms and Complexity Analysis - [Go2, CLR]

Chordal Graphs and their Applications - [Go4, Mc22]

Transitively Orderable Graphs - [Go5, Mc27.6]

Permutation Graphs - [Go7, Mc27.4]

Weakly Chordal Graphs and Strongly Chordal Graphs - [Mc27.3, Mc27.12, Go13]

Split Graphs, Threshold Graphs and CoGraphs - [Go6, Mc2 2.5, Go10 Mc25, Mc27.9]

Interval Graphs - [Go8, Mc23]

Tolerance Graphs - [GT1, GT2]

Interval Probe Graphs - [GT4, Mc23.4.1]

Intersection Graphs on Trees - [GT10, Mc22.3]

**Texts: **

Go:
M.C. Golumbic, *Algorithmic Graph Theory and Perfect Graphs*,

second
edition, Elsevier (2004).

Chapters 1; 2; 4(1-4, 6); 5(1,4,6-7); 6(1-2); 7(1-2,4-5); 8(1-4); 10; 13

GT:
M.C. Golumbic & A.N. Trenk, *Tolerance
Graphs*,

Cambridge
University Press (2004).

Chapters 1; 2(1-3,6-7); 4(1-4,7-8)

Other
references:

MP : Mahadev & Peled, Threshold Graphs and Related
Topics

BLS: Brandstadt,
Le & Spinrad, Graph Classes: A Survey

Mc2:
T.A. McKee & F.R. McMorris, Topics in
Intersection Graph Theory

Misc. papers from the literature

Students
are responsible for reading all assigned material. Exercises are to be
presented in class. Each student will
also be expected to concentrate on a paper from the literature to be assigned
in class and do a course project or presentation. The exam will be open book,
covering the material discussed in the lectures.

This
is a graduate elective course. Students
are expected to have mastered basic undergraduate knowledge of algorithms,
complexity analysis and discrete mathematics.