Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
type: Item
instance of: scholarly article
title: Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
zbMATH Open document ID: 1042.68088
DOI: 10.1016/S0020-0190(02)00268-5
author: Zhi-Zhong Chen
author: Shiqing Zhang
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1856466
zbMATH Keywords: Algorithms
zbMATH Keywords: Bipartite graphs
zbMATH Keywords: Edge bound
MaRDI profile type: Publication
cites work: An approach to the subgraph homeomorphism problem
cites work: Q5422499
cites work: The maximal \(f\)-dependent set problem for planar graphs is in NC
cites work: Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
cites work: Efficient algorithms for acyclic colorings of graphs
cites work: Parallel algorithms for maximal acyclic sets
cites work: On the edge numbers of graphs with Hadwiger number 4 and 5
cites work: A note on primitive skew curves
cites work: Q4763420
cites work: Extending planar graph algorithms to \(K_{3,3}\)-free graphs
cites work: NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
cites work: A Quick Proof of Wagner's Equivalence Theorem
description: scientific article; zbMATH DE number 1856466