Finding regular subgraphs in both arbitrary and planar graphs

DOI10.1016/0166-218X(95)00061-UzbMath0855.68071MaRDI QIDQ1923612

Iain A. Stewart

Publication date: 14 January 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (10)

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Construction of k-matchings in graph products ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Graph editing problems with extended regularity constraints ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Parameterized Graph Editing with Chosen Vertex Degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Problems complete for deterministic logarithmic space
• A new 5‐arc‐transitive cubic graph

This page was built for publication: Finding regular subgraphs in both arbitrary and planar graphs