Title | : | Cycle-extendability versus planarity |
Speaker | : | Nishad Kothari (IIT Madras) |
Details | : | Tue, Oct 18, 2022 3:00 PM, @ CSB 34 |
Abstract | : | For most problems pertaining to the study of perfect matchings, one may restrict attention
to the class of matching covered graphs (i.e., connected graphs with the property that each
edge belongs to some perfect matching). Such graphs are also known as 1-extendable graphs
- since each edge extends to a perfect matching. In the same spirit, we say that a matching
covered graph G is cycle-extendable if (either) perfect matching of any even cycle Q extends
to a perfect matching (of G) - which is equivalent to saying that G-V(Q) has a perfect
matching for each even cycle Q. There is extensive literature on the study of matching covered graphs, and one of the most important ingredients is an ear decomposition theory (similar to ear decomposition theory of 2-connected graphs). From this vantage point, a matching covered graph G is cycle-extendable if and only if each even cycle may be extended to an ear decomposition of G. As of now, there is no known NP characterization of cycle-extendable graphs (in general). Recently (July 2022), Zhang, Wang, Yuan, Ng and Cheng obtained such a characterization for cycle-extendable claw-free graphs (where claw-free means that there is no induced sub- graph isomorphic to K_{1,3}). We are currently working on obtaining NP characterizations of (i) cubic graphs and (ii) planar graphs that are cycle-extendable. In my recent talk (August 2022), I discussed the cubic bipartite case and its resolution. In this talk, I will be discussing the planar case — for which we have partial results (as of now), and a conjecture (that we are working on). This is on-going and joint work with Rajat Adak (IIT-H), Marcelo H. de Carvalho (UFMS Brazil), Ajit Diwan (IIT-B) and Kapil Pause (CMI). I will present the necessary background, and describe our aforementioned results. The talk will be self-contained. Note:This talk is a follow-up to my previous t-meet talk (30th August, 2022). If you missed that, or if you would like to refresh your memory, here is a handout to help you. |