A note on the complexity of finding regular subgraphs

DOI10.1016/0012-365X(84)90113-4zbMath0567.05029MaRDI QIDQ1059641

Ján Plesník

Publication date: 1984

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

zbMATH Keywords

NP-completenessdetecting regular subgraphs in a given graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph theory (05C99)

Related Items

Construction of k-matchings in graph products, The stable fixtures problem with payments, Graph factors and factorization: 1985--2003: a survey, On the complexity of nucleolus computation for bipartite \(b\)-matching games, Parameterized complexity of finding small degree-constrained subgraphs, Editing graphs to satisfy degree constraints: a parameterized approach, Addendum to: The complexity of regular subgraph recognition, Graph editing problems with extended regularity constraints, Graph theory (algorithmic, algebraic, and metric problems), Parameterized Graph Editing with Chosen Vertex Degrees

Cites Work

• Parallel concepts in graph theory
• On the berge—sauer conjecture
• On a problem of K. Zarankiewicz
• Three‐regular subgraphs of four‐regular graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item