| Title | : | Planar cycle-extendable graphs |
| Speaker | : | Dalwadi Aditya Yogeshbhai (IITM) |
| Details | : | Tue, 1 Oct, 2024 3:30 PM @ SSB 334 |
| Abstract: | : | A nontrivial connected graph G is said to be matching covered if each edge is part of some perfect matching. For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs — aka 1-extendable graphs since each edge extends to a perfect matching. In a similar fashion, we say that a matching covered graph G is cycle-extendable if (either) perfect matching of each even cycle Q extends to a perfect matching (of G). Equivalently, a matching covered graph is cycle-extendable if each even cycle can be expressed as a symmetric difference of two perfect matchings. Another motivation to work on cycle-extendable graphs arises from the ear decomposition theory of matching covered graphs (that is similar to the well-known ear decomposition theory of 2-connected graphs). From this viewpoint, a matching covered graph G is cycle-extendable if and only if each even cycle extends to an ear decomposition of G. As of now, there is no known NP characterization of cycle-extendable graphs (in general). Recently, we obtained NP (as well as P) characterizations of planar cycle-extendable graphs. Guo and Zhang (2004) obtained such a characterization for bipartite planar cycle-extendable graphs. We establish a characterization of all planar cycle-extendable graphs — in terms of K2 and four infinite families. As a first step, we reduce our problem to the class of “near-bricks†using a result of Carvalho and Little (2008). Thereafter, we reduce the minimum degree δ ≥ 3 case to “bricks†and prove that the only cycle-extendable planar simple bricks are wheels and prisms — using a result of Norine-Thomas (2007). For the δ = 2 case, we proceed by induction by bicontracting a vertex of degree two; this case comprises the bulk of our proof and case analysis. Two of the aforementioned four families are generalizations of wheels and prisms, whereas the other two are new families. This is joint work with Kapil Pause (CMI), Ajit Diwan (IIT Bombay) and Nishad Kothari. |
