Algebra and Combinatorics Seminar

Date: April 1, 2022

Time: 3:00PM - 4:00PM

Location: BLOC 302

Speaker: Chun-Hung Liu, TAMU

Title: A decomposition theorem for immersion-free graphs with no 3-edge-cut

Abstract: Structural decomposition theorems for graphs with forbidden minors and topological minors have been proved and led to many applications. Graph immersions is a notion related to graph minors and topological minors, and many analogous open problems about immersions have been proposed. In this talk we address the fundamental problem about the structure of a graph with forbidden immersions. We prove that every graph with no edge-cut of size 3 that forbids a fixed graph H as an immersion can be decomposed into graphs that are "nearly simpler" than H. The condition for having no 3-edge-cut is necessary to have a clean theorem.