Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.

DOI10.1016/S0020-0190(02)00268-5zbMath1042.68088MaRDI QIDQ1853125

Zhi-Zhong Chen, Shiqing Zhang

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

AlgorithmsBipartite graphsEdge bound

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

Local Hadwiger's conjecture ⋮ Fast algorithms for some dominating induced matching problems

Cites Work

• Unnamed Item
• Unnamed Item
• Extending planar graph algorithms to \(K_{3,3}\)-free graphs
• The maximal \(f\)-dependent set problem for planar graphs is in NC
• On the edge numbers of graphs with Hadwiger number 4 and 5
• An approach to the subgraph homeomorphism problem
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• Parallel algorithms for maximal acyclic sets
• Efficient algorithms for acyclic colorings of graphs
• Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
• A Quick Proof of Wagner's Equivalence Theorem
• A note on primitive skew curves

This page was built for publication: Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.