Nonseparating K4‐subdivisions in graphs of minimum degree at least 4

DOI10.1002/JGT.22247MaRDI QIDQ4553735zbMATH OpenOpenAlexFDO

Authors Matthias Kriesell

Publication date 31 October 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.5278

zbMATH Keywords

complete graphdecompositionminimum degreestructure theoremsubdivision

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: We first prove that for every vertex x of a 4-connected graph G there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that G-V(H) is connected and contains x. This implies an affirmative answer to a question of W. Kuehnel whether every 4-connected graph G contains a subdivision H of K4 as a subgraph such that G-V(H) is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4-connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredience of the proof where 4-connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4, by developing the respective motor: A structure theorem for the class of simple connected graphs of minimum degree at least 4.

Recommendations

• On graphs with no induced subdivision of \(K_4\)
• Some remarks on graphs with no induced subdivision of \(K_4\)
• Totally odd K₄-subdivisions in 4-chromatic graphs
• K₅^--subdivision in 4-connected graphs
• scientific article; zbMATH DE number 3941598
• The chromatic number of graphs with no induced subdivision of \(K_4\)
• scientific article; zbMATH DE number 554189
• scientific article; zbMATH DE number 1342091
• Nonseparating Cycles in 4-Connected Graphs
• Vertex partitions of \(K_{4,4}\)-minor free graphs

Cited in

(7)

• Generating internally four-connected graphs
• Reduction for 3-connected graphs of minimum degree at least four
• Counting \(K_4\)-subdivisions
• Linking four vertices in graphs of large connectivity
• scientific article; zbMATH DE number 1475184 (Why is no real title available?)
• Totally odd K₄-subdivisions in 4-chromatic graphs
• Subdivisions of maximal 3‐degenerate graphs of order d+1 d+1 in graphs of minimum degree d d

This page was built for publication: Nonseparating K₄‐subdivisions in graphs of minimum degree at least 4

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4553735)