Effective Term

2018 Winter Quarter

Learning Activities

Lecture - 3.0 hours

Discussion - 1.0 hours

Description

Fundamental concepts. Planar graphs: Kuratowski's theorem. Packings and coverings. Menger's theorem, representation of cuts, Hamilton graphs, rigid graphs, chordal graphs, graph coloring, graph isomorphism, applications and some algorithms.

Prerequisites

Graduate standing in electrical engineering or computer science or consent of instructor.

Enrollment Restrictions

Suppress CRN in Schedule.

Open to Graduate Students in Computer Science only.

**Summary of Course Content**

I. Fundamental Concepts

A. Handshake Lemma

B. Chicken Joke Lemma

C. Rice Farmers proof of Euler's equation

D. Perfect and impure graphs - Lovasz's theorem

II. Hamilton path and cycle

A. Planar graphs

B. Kurotowski's theorem

C. Five color theorem

D. Four color theorem

III. Connectivity and Cuts

A. Menger's theorem

B. Gomory-Hu trees

C. Cactus graphs

IV. Chordal graphs and applications

A. Equivalent definitions

B. Perfect elimination ordering

C. Clique Trees and graph decomposition

V. Rigid Graph Theory

A. Combinatorial analysis

B Topological analysis

C. Matroid analysis

VI. Graph Isomorphism

A. Heuristics

B. Exact methods

Project/Design Statement:

The course requires challenging homework of the theorem-proof type. No project.

**Illustrative Reading**

Course readings selected from a variety of sources.

One suggested reference is: Graph Theory. Graduate texts in Mathematics. J.A. Bondy and U.S.R. Murty. Springer 2008.

**Potential Course Overlap**

This course does not have a significant overlap with any other course, although a few of the topics might be taught in some math courses.

**Final Exam**

Yes Final Exam

**Justification for No Final Exam**

None

## Course Category