Odd K₃,3 subdivisions in bipartite graphs

DOI10.1016/J.JCTB.2016.01.005MaRDI QIDQ256986zbMATH OpenOpenAlexFDO

Authors Robin Thomas, Peter Whalen

Publication date 14 March 2016

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

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

zbMATH Keywords

bipartite graphodd \(K_{3, 3}\) subdivisionPfaffian orientation

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that every internally 4-connected non-planar bipartite graph has an odd K_3,3 subdivision; that is, a subgraph obtained from K_3,3 by replacing its edges by internally disjoint odd paths with the same ends. The proof gives rise to a polynomial-time algorithm to find such a subdivision. (A bipartite graph G is internally 4-connected if it is 3-connected, has at least five vertices, and there is no partition (A,B,C) of V(G) such that |A|,|B|>1, |C|=3 and G has no edge with one end in A and the other in B.)

Recommendations

• Finding an odd \(K_{3,3}\)
• A planarity criterion for cubic bipartite graphs
• Edges and Kuratowski Subgraphs of Non-Planar Graphs
• Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
• Matching covered graphs and subdivisions of \(K_ 4\) and \(\bar C_ 6\)

Cites work

• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A characterization of convertible (0,1)-matrices
• A survey of Pfaffian orientations of graphs
• Graph theory
• Permanents, Pfaffian orientations, and even directed circuits
• Pólya's permanent problem
• The complexity of computing the permanent
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

Cited in

(3)

• Counting the number of perfect matchings, and generalized decision trees
• A planarity criterion for cubic bipartite graphs
• Generating internally four-connected graphs

This page was built for publication: Odd \(K_{3,3}\) subdivisions in bipartite graphs

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