Shanshan Zhang ; Xiumei Wang ; Jinjiang Yuan - Even cycles and perfect matchings in claw-free plane graphs

dmtcs:6062 - Discrete Mathematics & Theoretical Computer Science, October 12, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-6
Even cycles and perfect matchings in claw-free plane graphsArticle

Authors: Shanshan Zhang ; Xiumei Wang ; Jinjiang Yuan

    Lov{á}sz showed that a matching covered graph G has an ear decomposition starting with an arbitrary edge of G. Let G be a graph which has a perfect matching. We call G cycle-nice if for each even cycle C of G, GV(C) has a perfect matching. If G is a cycle-nice matching covered graph, then G has ear decompositions starting with an arbitrary even cycle of G. In this paper, we characterize cycle-nice claw-free plane graphs. We show that the only cycle-nice simple 3-connected claw-free plane graphs are K4, W5 and ¯C6. Furthermore, every cycle-nice 2-connected claw-free plane graph can be obtained from a graph in the family F by a sequence of three types of operations, where F consists of even cycles, a diamond, K4, and ¯C6.


    Volume: vol. 22 no. 4
    Section: Graph Theory
    Published on: October 12, 2020
    Accepted on: August 30, 2020
    Submitted on: January 31, 2020
    Keywords: Mathematics - Combinatorics,05C70

    Classifications

    Consultation statistics

    This page has been seen 668 times.
    This article's PDF has been downloaded 514 times.