Difference of forbidden pairs containing a claw

2015/05/03 by Guantao Chen, Chen, Guantao, Michitaka Furuya +7
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1505.00386

21 pages, 6 figures

arxiv created 2015/05/03 · arxiv updated 2015/05/05

Abstract

When we study forbidden subgraph conditions guaranteeing graphs to have some properties, a claw (or K_1,3) frequently appears as one of forbidden subgraphs. Recently, Furuya and Tsuchiya compared two classes generated by different forbidden pairs containing a claw, and characterized one of such classes. In this paper, we give such characterization for three new classes. Furthermore, we give applications of our characterizations to some forbidden subgraph problems.

Related

• Forbidding the subdivided claw as a subgraph or a minor
• Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4
• Strongly Perfect Claw-free Graphs -- A Short Proof
• Characterizing forbidden pairs for spanning \varTheta-subgraphs of 2-connected graphs
• Forbidden pairs and the existence of a dominating cycle