IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Coloring graphs containing no K5-subdivision

  • Oct. 1, 2021
  • 2:30 p.m.


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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster