Loading Events

View All Events »

Mathematics Colloquium – Matching Theory: $K_4$-based and $\overline{C_6}$-based Planar Graphs

September 29 @ 4:30 pm - 5:30 pm

  • This event has passed.

Event Details

Speaker: Nishad Kothari, Assistant Professor, Department of Computer Science and Engineering, IIT Madras

Abstract: For several problems in Matching Theory, one may restrict attention to matching covered graphs — i.e., connected graphs with the additional property that each edge belongs to some perfect matching. Two types of decompositions — ear decompositions and tight cut decompositions — play an important role in the study of these graphs.
Lov{\’a}sz (1983) proved that every nonbipartite matching covered graph admits an ear decomposition starting from a bi-subdivision of the complete graph~$K_4$, or from a bi-subdivision of the triangular prism~$\overline{C_6}$. This gives rise to two natural problems: Which matching covered graphs are $K_4$-based (i.e. admit an ear decomposition starting from a bi-subdivision of $K_4$)? Likewise, which ones are $\overline{C_6}$-based?
In a joint work with U. S. R. Murty (https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.21882), we solved the aforementioned problems for planar graphs. At a high level, our solution comprises two steps: (i) reduce each problem to the case of “bricks” (special nonbipartite matching covere graphs) by applying the tight cut decomposition, and (ii) solve each problem for the case of planar bricks. I will discuss each of these problems, and our solutions for the planar case.


September 29
4:30 pm - 5:30 pm