✦ LIBER ✦

On locating cubic subgraphs in bounded-degree connected bipartite graphs

✍ Scribed by Iain A Stewart

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 236 KB
Volume: 163
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00324-p

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the problem of deciding whether a connected bipartite graph of degree at most 4 has a cubic subgraph is NP-complete.

📜 SIMILAR VOLUMES

Long Cycles and 3-Connected Spanning Sub

Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected K1, d-Free Graphs

✍ B. Jackson; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Let \(G\) be a 3-connected \(K_{1, d}\)-free graph on \(n\) vertices. We show that \(G\) contains a 3-connected spanning subgraph of maximum degree at most \(2 d-1\). Using an earlier result of ours, we deduce that \(G\) contains a cycle of length at least \(\frac{1}{2} n^{c}\) where \(c=\left(\log