Online Talk: Jagdeep Singh

Tuesday, Oct 5, 3pm ET (8pm BST, 8am Wed NZST)
Jagdeep Singh, Louisiana State University
$2$-Cographs and Binary Comatroids

The well-known class of cographs or complement-reducible graphs is the class of graphs that can be generated from $K_1$ using the operations of disjoint union and complementation. In this talk, we consider $2$-cographs, a natural generalization of cographs, and binary comatroids, a matroid analogue. We show that, as with cographs, both $2$-cographs and binary comatroids can be recursively defined. However, unlike cographs, $2$-cographs and binary comatroids are closed under induced minors. We consider the class of non-$2$-cographs for which every proper induced minor is a $2$-cograph and show that this class is infinite. Our main result for graphs finds the finitely many members of this class whose complements are also  induced-minor-minimal non-$2$-cographs. In the matroid case, our main result identifies all binary non-comatroids for which every proper flat is a binary comatroid. This is joint work with James Oxley.


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.