| Title | : | From Cographs to Comatroids: Forbidden Structures and Apex Classes |
| Speaker | : | Jagdeep Singh (Mississippi State University.) |
| Details | : | Tue, 28 Oct, 2025 4:00 PM @ Online |
| Abstract: | : | Complement reducible graphs, or cographs, form one of the most well-understood hereditary classes of graphs: they admit linear-time recognition, possess multiple elegant characterizations, and have a simple forbidden subgraph description (no induced path of length three). In this talk, I will describe two natural generalizations of cographs; 2-cographs and sesquicographs. I will then present results showing that apexing (adding a single vertex or edge) preserves the finiteness of forbidden induced subgraphs, along with explicit bounds on their size. Finally, I will extend this framework from graphs to binary matroids, introducing comatroids as the natural matroid analogue of cographs. Analogous extension results hold in this setting. This work includes joint work with James Oxley (Electron. J. Combin., SIAM J. Discrete Math.), Thomas Zaslavsky and Vaidy Sivaraman (Discrete Math.) LINK: meet.google.com/agg-kgrr-ycp |
