Odd K₃,3 subdivisions in bipartite graphs
From MaRDI portal
Publication:256986
DOI10.1016/J.JCTB.2016.01.005zbMATH Open1332.05116arXiv1309.5336OpenAlexW2962719609MaRDI QIDQ256986FDOQ256986
Authors: Robin Thomas, Peter Whalen 
Publication date: 14 March 2016
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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.)
Full work available at URL: https://arxiv.org/abs/1309.5336
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\)
Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Graph theory
- Pólya's permanent problem
- A characterization of convertible (0,1)-matrices
- Permanents, Pfaffian orientations, and even directed circuits
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
- A survey of Pfaffian orientations of graphs
- Title not available (Why is that?)
- The complexity of computing the permanent
Cited In (3)
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)
