Topological containment of the 5-clique minus an edge in 4-connected graphs

2017/05/03 by Rebecca Robinson, Robinson, Rebecca, Graham Farr +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #Graph theory and applications #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1705.01224

26 pages, 14 figures

openalex publication_date 2017/05/03 · arxiv created 2017/05/04 · arxiv updated 2017/05/05 · openalex created_date 2017/05/12 · openalex updated_date 2026/07/28

Abstract

The topological containment problem is known to be polynomial-time solvable for any fixed pattern graph H, but good characterisations have been found for only a handful of non-trivial pattern graphs. The complete graph on five vertices, K₅, is one pattern graph for which a characterisation has not been found. The discovery of such a characterisation would be of particular interest, due to the Hajós Conjecture. One step towards this may be to find a good characterisation of graphs that do not topologically contain the simpler pattern graph K₅^-, obtained by removing a single edge from K₅. This paper makes progress towards achieving this, by showing that every 4-connected graph must contain a K₅^--subdivision.

Related

• 4-Separations in Hajós Graphs
• Wheels in planar graphs and Hajós graphs
• On the Minimum Number of Edges in Triangle-Free 5-Critical Graphs
• The Kelmans-Seymour conjecture I: special separations
• Induced subgraph density. VII. The five-vertex path