| Title | : | Planar cycle-extendable graphs and related classes |
| Speaker | : | Dalwadi Aditya Yogeshbhai (IITM) |
| Details | : | Tue, 28 Jan, 2025 11:00 AM @ Turing Hall |
| Abstract: | : | A nontrivial connected graph is matching covered if each edge participates in 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, a matching covered graph G is cycle-extendable if (either) perfect matching of each of its even cycles extends to a perfect matching (of G), or equivalently, if each of its even cycles is the symmetric difference of two perfect matchings (of G). Another motivation to study cycle-extendable graphs arises from the ear decomposition theory of matching covered graphs due to Hetyei, Lovász and Plummer (that is similar to Whitney's ear decomposition theorem for 2-connected graphs). From this viewpoint, a matching covered graph G is cycle-extendable if each of its even cycles 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; earlier, special cases of this were settled in particular, the bipartite case by Guo and Zhang (Discrete Mathematics, 2004), and the claw-free case by Zhang, Wang and Yuan (Discrete Mathematics & Theoretical Computer Science, 2020). We establish a characterization of all planar cycle-extendable graphs in terms of K2 and four infinite families. This work - co-authored with Kapil R. Senvi Pause (CMI), the late Ajit Diwan (IIT-B) and Nishad Kothari (IIT-M) has been submitted to Discrete Mathematics & Theoretical Computer Science. We briefly describe our approach. Firstly, we note that it suffices to characterize irreducible graphs that is, those simple graphs whose degree two vertices comprise a stable set. Secondly, we use a result of Carvalho and Little (The Electronic Journal of Combinatorics, 2008) to observe that every cycle-extendable graph is either bipartite or a "near-brick". Thereafter, we reduce the minimum degree 8 3 case to "bricks" and prove that the only cycle-extendable planar simple bricks are wheels and prisms using the brick generation theorem of Norine and Thomas (Journal of Combinatorial Theory Series B, 2007). For the 8 = 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. We mention two related graph classes that may also be defined in terms of extendability of (perfect matchings of) their even cycles. A matching covered graph G is cycle-forced if (either) perfect matching of each of its even cycles extends to precisely one perfect matching (of G). We observed that the class of cycle-forced graphs is indeed the intersection of: (i) cycle-extendable graphs, and (ii) another well-studied class "PM-compact" graphs that is inspired by the perfect matching polytope. Additionally, we establish a characterization of bipartite planar cycle-forced graphs in terms of their ear decompositions. In our study of cycle-extendable graphs, we observed that the planar ones comprise a proper subset of K2,3-free graphs - that is, those matching covered graphs that do not contain any bisubdivision of K2,3 as a subgraph. In fact, in the case of bipartite graphs, K2,3-free ones are precisely the planar cycle- extendable ones. However, in the nonplanar case, these two classes are unrelated. We characterize three special cases of K2,3-free graphs: (i) 3-connected, (ii) 3-regular, and (iii) "bicritical". Finally, we conjecture that every nonbipartite K2,3-free graph is a "near-brick". |
