Critical (P₅,W₄)-Free Graphs

2025/01/09 by Xia Wen, Xia, Wen, Jorik Jooken +9
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2501.04923

Abstract

A graph G is k-vertex-critical if χ(G) = k but χ(G-v)

Related

• Infinite families of k-vertex-critical (P₅, C₅)-free graphs
• Vertex-critical (P₃+ℓ P₁)-free and vertex-critical (gem, co-gem)-free graphs
• Vertex-critical graphs in co-gem-free graphs
• Vertex-Critical (P₅, chair)-Free Graphs
• On the finiteness of k-vertex-critical 2P₂-free graphs with forbidden induced squids or bulls