Skip to Content

Sponsors

No results

Tags

No results

Types

No results

Search Results

Events

No results
Search events using: keywords, sponsors, locations or event type
When / Where
All occurrences of this event have passed.
This listing is displayed for historical purposes.

Presented By: Department of Mathematics

Colloquium Series

Induced subgraphs and coloring

What causes a graph to have high chromatic number? One reason is that the graph may contain a large set of pairwise adjacent vertices (called a "clique"), but what can be said if that is not the case? Around 1985 Andras Gayfas made three conjectures about structures that must be present in a graph with large chromatic number all of whose cliques have bounded size. Recently we proved the strongest of these conjectures, that implies the other two. In this talk we will discuss some of the proof ideas, and related problems and theorems. Speaker(s): Maria Chudnovsky (Princeton University)

Explore Similar Events

  •  Loading Similar Events...

Back to Main Content