Coloring graphs containing no K_5-subdivision

-
Abstract

The well-known Four Color Theorem states that graphs containing no K_5-subdivision or K_{3,3}-subdivision are 4-colorable. It was conjectured by Hajós that graphs containing no K_5-subdivision are also 4-colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture is 4-connected but not 5-connected. We show that any such counterexample does not admit a 4-cut with a nontrivial planar side. This is joint work with Qiqin Xie, Shijie Xie and Xingxing Yu.

Description

Postdoc Seminar
Monday, April 17
11:45am - 1:00pm
WXLR A206

Pizza will be served at 11:45am. Talk begins at 12:00pm.
 

Speaker

Xiaofan Yuan
Postdoc
Arizona State University

Location
WXLR A206