✦ LIBER ✦
Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application
✍ Scribed by Zhi-Zhong Chen; Shiqing Zhang
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 68 KB
- Volume
- 84
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
We show that an n-vertex bipartite K 3,3 -free graph with n 3 has at most 2n -4 edges and that an n-vertex bipartite K 5 -free graph with n 5 has at most 3n -9 edges. These bounds are also tight. We then use the bound on the number of edges in a K 3,3 -free graph to extend two known NC algorithms for planar graphs to K 3,3 -free graphs.