A refinement of Kuratowski's theorem

DOI10.1016/0095-8956(84)90057-1MaRDI QIDQ800369zbMATH OpenOpenAlexFDO

Authors Carsten Thomassen

Publication date 1984

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(84)90057-1

zbMATH Keywords

cycle with crossing chordsKuratowski's theoremplanarity criterion

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

A chord of a cycle C is an edge not in C but joining two vertices of C. This paper settles in the affirmative the following conjecture of Kelmans (Problem at the 6th Hungarian Colloquium on Combinatorics, Eger, 1981): If G is a 3-connected non-planar graph of order six or more, then G has a cycle with three pairwise crossing chords. This result is then used to establish a refinement of Kuratowski's theorem, for which a class \({\mathcal C}\) of graphs is defined by: (i) \(K_ 5\) and each planar 3-connected graph are in \({\mathcal C}\); (ii) if \(e_ 1=x_ 1y_ 1\) and \(e_ 2=x_ 2y_ 2\) are edges of disjoint graphs \(G_ 1\) and \(G_ 2\), respecively, in \({\mathcal C}\), then the graph obtained from \(G_ 1\cup G_ 2\) by identifying \(x_ 1\) with \(y_ 1\) and \(x_ 2\) with \(y_ 2\) and possibly deleting \(e_ 1\) and \(e_ 2\) is also in \({\mathcal C}\). Then the refinement is: Any 2-connected graph G satisfies precisely one of: (1) G is in \({\mathcal C}\); (2) G contains a cycle C with six vertices \(x_ 1\), \(x_ 2,...,x_ 6\) in that cyclic order such that, for each \(i=1,2,3\), either \(x_ ix_{i+3}\) is an edge of G or \(G-\{x_ i,x_{i+3}\}\) has a connected component \(H_ i\) not intersecting C.

Recommendations

• A strengthening of the Kuratowski planarity criterion for 3-connected graphs
• Edges and Kuratowski Subgraphs of Non-Planar Graphs
• Kuratowski chains
• Every longest circuit of a 3‐connected,K_3,3‐minor free graph has a chord
• scientific article; zbMATH DE number 475620

Cites work

• Efficient Planarity Testing
• scientific article; zbMATH DE number 3133252 (Why is no real title available?)
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• Kuratowski's theorem
• Non-separating induced cycles in graphs
• Planarity and duality of finite and infinite graphs

Cited in

(19)

• Cycles of length 0 modulo 4 in graphs
• On a refinement of Ado's theorem
• A planarity criterion for cubic bipartite graphs
• Kuratowski chains
• Refinements of the Kiefer-Wolfowitz theorem and a test of concavity
• Convex grid drawings of planar graphs with constant edge-vertex resolution
• Refining Rossberg's theorem
• Jordan circuits of a graph
• A theorem of Krein revisited
• A REFINEMENT OF KOBLITZ'S CONJECTURE
• scientific article; zbMATH DE number 3842171 (Why is no real title available?)
• Topological minors in line graphs -- a proof of Zha's conjecture
• Classes of cubic graphs containing cycles of integer-power lengths
• A Practical Approach to Courcelle's Theorem
• On colorability of graphs with forbidden minors along paths and circuits
• Strictly-convex drawings of 3-connected planar graphs
• Convex grid drawings of planar graphs with constant edge-vertex resolution
• A strengthening of the Kuratowski planarity criterion for 3-connected graphs
• A Kuratowski-Mrówka theorem in approach theory

This page was built for publication: A refinement of Kuratowski's theorem

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