𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs

✍ Scribed by Mohammadtaghi Hajiaghayi; Naomi Nishimura; Prabhakar Ragde; Dimitrios M. Thilikos

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
227 KB
Volume
10
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Every longest circuit of a 3-connected,
Every longest circuit of a 3-connected, K3,3-minor free graph has a chord
✍ Etienne BirmelΓ© πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 142 KB πŸ‘ 1 views

## Abstract Carsten Thomassen conjectured that every longest circuit in a 3‐connected graph has a chord. We prove the conjecture for graphs having no __K__~3,3~ minor, and consequently for planar graphs. Β© 2008 Wiley Periodicals, Inc. J Graph Theory 58: 293–298, 2008

Efficient Approximation Schemes for Maxi
Efficient Approximation Schemes for Maximization Problems onK3, 3-free orK5-free Graphs
✍ Zhi-Zhong Chen πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 263 KB

We show that for any integer k G 2 and any n-vertex graph G without a K 3, 3 Ε½ . or K minor, one can compute k induced subgraphs of G with treewidth no more 5 Ε½ . Ε½. Ε½ Ε½ 2 .. than 3k y 4 respectively, 6 k y 7 in O kn respectively, O kn q n time such that each vertex of G appears in exactly k y 1 of

Tight upper bound on the number of edges
Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application
✍ Zhi-Zhong Chen; Shiqing Zhang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 68 KB

We show that an n-vertex bipartite K 3,3 -free graph with n 3 has at most 2n -4 edges and that an n-vertex bipartite K 5 -free graph with n 5 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 fo