Name
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.) |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Discrete mathematics,Complete bipartite graph,Odd graph,Combinatorics,Edge-transitive graph,Forbidden graph characterization,Graph factorization,Folded cube graph,Bipartite graph,Matching (graph theory),Mathematics |
DocType | Volume | Citations |
Journal | abs/1309.5336 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robin Thomas | 1 | 466 | 52.08 |
| Peter Whalen | 2 | 14 | 2.42 |