Speaker: |
Nishad Kothari (The University of Campinas SP, Brazil) |

Organiser: |
Umang Bhaskar |

Date: |
Tuesday, 19 Feb 2019, 14:30 to 15:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

Recently, in a joint work with Marcelo H. de Carvalho, Xiumei Wang and Yixun Lin, we considered the "intersection" of these graph classes. We give a complete characterization of graphs that are Birkhoff-von Neumann as well as PM-compact. Consequently, the corresponding decision problem is in P. Earlier, in a joint work with Claudio L. Lucchesi, Marcelo H. de Carvalho and U. S. R. Murty, we showed that the problem of deciding whether a graph G is Birkhoff-von Neumann is equivalent to the seemingly unrelated problem of deciding whether G is `prism-free'.

I will discuss the two problems, and our recent results mentioned above. The talk will be mostly self-contained. I will assume only basic knowledge of graph theory. I will perhaps not present any lengthy proofs. For more details, see: https://arxiv.org/abs/1807.07339 and

https://epubs.siam.org/doi/abs/10.1137/17M1138704.