Critical (P₅,bull)-free graphs

2022/11/08 by Shenwei Huang, Jiawei Li, Huang, Shenwei +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2211.04179

openalex publication_date 2022/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given two graphs H₁ and H₂, a graph is (H₁,H₂)-free if it contains no induced subgraph isomorphic to H₁ or H₂. Let P_t and C_t be the path and the cycle on t vertices, respectively. A bull is the graph obtained from a triangle with two disjoint pendant edges. In this paper, we show that there are finitely many 5-vertex-critical (P₅,bull)-free graphs.

Related

• Structural description of (bull, house)-free graphs
• There are finitely many 5-vertex-critical (P₆,bull)-free graphs
• Vertex-Critical (P₅, chair)-Free Graphs
• k-Critical Graphs in P₅-Free Graphs
• Critical (P₅,dart)-Free Graphs