BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Ashoka University - ECPv6.18.2//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://www.ashoka.edu.in
X-WR-CALDESC:Events for Ashoka University
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20200919T163000
DTEND;TZID=UTC:20200919T173000
DTSTAMP:20211006T191416Z
CREATED:20211006T191416Z
LAST-MODIFIED:20211006T191416Z
UID:20095-1600533000-1600536600@www.ashoka.edu.in
SUMMARY:Matching Theory: K4-based and C6-based Planar Graphs
DESCRIPTION: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.\nLov´asz (1983) proved that every nonbipartite matching covered graph admits an ear decomposition starting from a bi-subdivision of the complete graph K4\, or from a bi-subdivision of the triangular prism C6. This gives rise to two natural problems: Which matching covered graphs are K4-based (i.e.\, admit an ear decomposition starting from a bi-subdivision of K4)? Likewise\, which ones are C6-based?\nIn 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 highlevel\, 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.\nI will discuss each of these problems\, and our solutions for the planar case.
URL:https://www.ashoka.edu.in/event/matching-theory-k4-based-and-c6-based-planar-graphs/
CATEGORIES:Online Event
END:VEVENT
END:VCALENDAR