Graphs, Matroids, Cographs and Comatroids
“If a theorem about graphs can be expressed in terms of edges and circuits only it probably exemplifies a more general theorem about matroids.” These words of Bill Tutte from 1979 have had a profound influence on research in matroid theory. This talk will discuss an example of recent work that was motivated by Tutte’s guiding principle. The class of cographs or complement- reducible graphs is the class of graphs that can be generated from K1 using the operations of disjoint union and complementation. We define 2-cographs to be the graphs we get by also allowing the operation of 1-sum. By analogy, we introduce the class of binary comatroids as the class of matroids that can be generated from the empty matroid using the operations of direct sum and taking complements inside of binary projective space. This talk will explore the properties of 2-cographs and binary comatroids. The main results characterize these classes in terms of forbidden induced minors. This is joint work with Jagdeep Singh.