Graph coloring and graph structure

-
Type
Abstract

Bounding the chromatic number of a graph can be difficult. On the other hand, graph structure can be helpful for bounding the chromatic number. For instance, the Four-Color Theorem states that graphs containing no subdivision of $K_5$ or $K_{3,3}$  are 4-colorable. We will discuss several classes of graphs with forbidden configurations, as well as bounds on the chromatic number of those graphs including possible generalizations of the Four-Color Theorem. We will mention some recent progress on those problems obtained by studying graph structures.

Description

Colloquium
Wednesday, September 25
1:30pm MST/AZ
WXLR A206

Speaker

Xingxing Yu
Professor and Director of Graduate Studies
Georgia Tech

Location
WXLR A206