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 | ¿ 2 , | C | = 3 and G has no edge with one end in A and the other in B.) |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.jctb.2016.01.005 | J. Comb. Theory, Ser. B |
Keywords | DocType | Volume |
Bipartite graph,Odd K3,3 subdivision,Pfaffian orientation | Journal | 118 |
Issue | ISSN | Citations |
C | 0095-8956 | 0 |
PageRank | References | Authors |
0.34 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robin Thomas | 1 | 457 | 35.92 |
| Peter Whalen | 2 | 14 | 2.42 |