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
scientific article
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 |
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