Contractibility and NP-completeness
From MaRDI portal
Publication:3739139
DOI10.1002/jgt.3190110111zbMath0603.05016OpenAlexW2105722028MaRDI QIDQ3739139
Andries E. Brouwer, Henk Jan Veldman
Publication date: 1987
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/1770
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Increasing the Minimum Degree of a Graph by Contractions, On the parameterized complexity of maximum degree contraction problem, Modulo orientations and matchings in graphs, Detecting induced star-like minors in polynomial time, Increasing the minimum degree of a graph by contractions, Detecting induced minors in AT-free graphs, On the parameterized complexity of grid contraction, Disconnected cuts in claw-free graphs, The complexity of contracting bipartite graphs into small cycles, On graph contractions and induced minors, Edge contractions in subclasses of chordal graphs, Contracting planar graphs to contractions of triangulations, Unnamed Item, Contracting graphs to paths and trees, Parameterizing cut sets in a graph by the number of their components, Parameterized complexity of three edge contraction problems with degree constraints, Path Contraction Faster than $2^n$, Edge Contractions in Subclasses of Chordal Graphs, Improved kernel results for some FPT problems based on simple observations, Contracting to a longest path in H-free graphs, On the Parameterized Complexity of Maximum Degree Contraction Problem., On the complexity of colouring by superdigraphs of bipartite graphs, Detecting fixed patterns in chordal graphs in polynomial time, Contracting chordal graphs and bipartite graphs to paths and trees, Contracting bipartite graphs to paths and cycles, Contracting bipartite graphs to paths and cycles, Contracting chordal graphs and bipartite graphs to paths and trees, Partitioning Graphs into Connected Parts, Path Contraction Faster Than 2^n, Containment relations in split graphs, Partitioning graphs into connected parts, Generalized partitions of graphs, Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs, Hereditarily hard \(H\)-colouring problems, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
