ECS 225: Graph Theory

Subject
ECS 225
Title
Graph Theory
Status
Active
Units
4.0
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

Graduate