A forbidden pair for quasi 5-contractible edges

2025/08/12 by Kou, Shuai, Yang, Weihua, Zhang, Mingzu +1
#05C40 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.08563

Abstract

An edge of a quasi k-connected graph is said to be quasi k-contractible if the contraction of the edge results in a quasi k-connected graph. If every quasi k-connected graph without a quasi k-contractible edge has either H₁ or H₂ as a subgraph, then an unordered pair of graphs \H₁, H₂\ is said to be a forbidden pair for quasi k-contractible edges. We prove that \K₄^-, P₅\ is a forbidden pair for quasi 5-contractible edges, where K₄^- is the graph obtained from K₄ by removing just one edge and P₅ is the complement of a path on five vertices.

Related

• Contractible Subgraphs of Contraction Critically Quasi 5-Connected Graphs
• A degree sum condition for the existence of a quasi 5-contractible edge in a quasi 5-connected graph
• Contractible Non-Edges in 3-Connected Graphs
• Characterizing the forbidden pairs for graphs to be super-edge-connected
• A Note on Contractible Edges in Chordal Graphs