Algebra and Combinatorics Seminar

Date: September 21, 2018

Time: 3:00PM - 4:00PM

Location: BLOC 628

Speaker: Chun-Hung Liu, Texas A&M University

Title: Clustered coloring on old graph coloring conjectures

Abstract: The famous Four Color Theorem states that every graph that can be drawn in the plane without edge-crossing is properly 4-colorable, which means that one can color its vertices with 4 colors such that every pair of adjacent vertices receive different colors. It is equivalent to say that every graph that does not contain a subgraph contractible to K_5 or K_{3,3} is properly 4-colorable. Hadwiger in 1943 proposed a far generalization of the Four Color Theorem: every graph that does not contain a subgraph contractible to K_{t+1} is properly t-colorable. Hajos, and Gerards and Seymour, respectively, proposed two strengthening of Hadwiger's conjecture, where only special kinds of edges are allowed to be contracted. More precisely, these three conjectures state that every graph that does no contain K_{t+1} as a minor (topological minor, or odd minor, respectively) is properly t-colorable. These three conjectures are either open or false, except for some very small t. One weakening of these three conjectures is to color the vertices such that every monochromatic component has bounded size, which is called clustered coloring. In this talk we will show joint work with David Wood about a series of tight results about clustered coloring on graphs with no subgraph isomorphic to a fixed complete bipartite graph. These results have a number of applications, including nearly optimal or first linear bound for the number of colors on the clustered coloring version of the previous three conjectures, as well as results on graphs embeddable in a surface of bounded genus where edge-crossings are allowed. No background about graph theory is required for this talk.