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
    0 references
    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

    Identifiers