{
  "id": "1309.5336",
  "version": "v1",
  "published": "2013-09-20T17:48:36.000Z",
  "updated": "2013-09-20T17:48:36.000Z",
  "title": "Odd K_3,3 subdivisions in bipartite graphs",
  "authors": [
    "Robin Thomas",
    "Peter Whalen"
  ],
  "comment": "12 pages, 1 figure",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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.)",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-09-20T17:48:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "subdivision",
      "non-planar bipartite graph",
      "internally disjoint odd paths",
      "polynomial-time algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1309.5336T"
    }
  }
}