SPLITTING NUMBER is NP-complete

DOI10.1016/S0166-218X(00)00220-1zbMath0969.68110WikidataQ127179013 ScholiaQ127179013MaRDI QIDQ5928869

Candido F. X. Mendonça, Celina M. Herrera de Figueiredo, Luérbio Faria

Publication date: 7 October 2001

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

zbMATH Keywords

PLANAR SUBGRAPHSPLITTING NUMBER

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 (8)

Splitting plane graphs to outerplanarity ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ An FPT algorithm for bipartite vertex splitting ⋮ Boundary graph classes for some maximum induced subgraph problems ⋮ On the planar split thickness of graphs ⋮ On maximum planar induced subgraphs ⋮ Unnamed Item ⋮ On the complexity of the approximation of nonplanarity parameters for cubic graphs

Cites Work

• The splitting number of complete bipartite graphs
• The splitting number of the complete graph
• Planarizing Graphs - A Survey and Annotated Bibliography
• Edge-Deletion Problems
• Efficient Planarity Testing
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item

This page was built for publication: SPLITTING NUMBER is NP-complete