# Topics in Discrete Mathematics: Induced Subgraphs

MAT 579

1252

1252

Info tab content

This course begins with a general introduction to the standard theorems about induced subgraphs, then go on to survey some recent work. Two central conjectures are (i) the Erdos-Hajnal conjecture, that every graph H, there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of size at least |G|^c, and (ii) the Gyarfas-Sumner conjecture, that for every tree H and every integer k, there exists c such that every graph not containing H as an induced subgraph and with clique number at most k, has chromatic number at most c. Attempts to prove these two conjectures are themes throughout.

Instructors tab content

Sections tab content

## Section C01

- Type: Class
- Section: C01
- Status: O
- Enrollment: 1
- Capacity: 20
- Class Number: 22442
- Schedule: TTh 11:00 AM-12:20 PM