Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application. (Q1853125)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application. |
scientific article; zbMATH DE number 1856466
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application. |
scientific article; zbMATH DE number 1856466 |
Statements
Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application. (English)
0 references
21 January 2003
0 references
We show that an \(n\)-vertex bipartite \(K_{3,3}\)-free graph with \(n\geqslant3\) has at most \(2n-4\) edges and that an \(n\)-vertex bipartite \(K_{5}\)-free graph with \(n\geqslant5\) 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.
0 references
Algorithms
0 references
Bipartite graphs
0 references
Edge bound
0 references
0 references
