Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
From MaRDI portal
Publication:4376161
Recommendations
- NP-completeness of graph decomposition problems
- Polynomial cases of graph decomposition: A complete solution of Holyer's problem
- On a decomposition of complete graphs
- Decompositions of Complete Graphs
- On the completeness of decomposable properties of graphs
- Decomposing the complete \(r\)-graph
- On decompositions of complete hypergraphs
- scientific article; zbMATH DE number 2197887
- Complete decomposable graphs
Cited in
(70)- A proof of the Barát-Thomassen conjecture
- Monochromatic clique decompositions of graphs
- Decomposing graphs into paths of fixed length
- Optimizing regenerator cost in traffic grooming
- Edge decompositions and rooted packings of graphs
- Spanning cubic graph designs
- Decomposing cubic graphs into connected subgraphs of size three
- Combinatorial and computational aspects of graph packing and graph decomposition
- Packing 1-plane Hamiltonian cycles in complete geometric graphs
- Inapproximability of \(H\)-transversal/packing
- Packing plane spanning graphs with short edges in complete geometric graphs
- Fractional clique decompositions of dense graphs and hypergraphs
- How to allocate review tasks for robust ranking
- Decompositions of highly connected graphs into paths of length 3
- FORK-DECOMPOSITION OF DIRECT PRODUCT OF GRAPHS
- The real truth about star designs
- P4-Decomposition of Total Graphs
- Integer and fractional packings of hypergraphs
- Towards a solution of the Holyer's problem
- Input-output decomposition of dynamic systems is NP-complete
- Decomposing semi-complete multigraphs and directed graphs into paths of length two
- Edge-decompositions of graphs with high minimum degree
- The weak 3-flow conjecture and the weak circular flow conjecture
- Decomposing graphs of high minimum degree into 4-cycles
- Perfectly packing graphs with bounded degeneracy and many leaves
- Partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple 4 order cycle
- Turán function and H-decomposition problem for gem graphs
- Multigraph decomposition into stars and into multistars
- Decomposing subcubic graphs into claws, paths or triangles
- On some multigraph decomposition problems and their computational complexity
- Partitions of complete bipartite geometric graphs into plane perfect matchings
- Decomposing dense bipartite graphs into 4-cycles
- Traffic grooming on the path
- On rooted packings, decompositions, and factors of graphs
- Packing 3-vertex paths in claw-free graphs and related topics
- Path decompositions of regular graphs with prescribed girth
- Decompositions of highly connected graphs into paths of any given length
- Decompositions of highly connected graphs into paths of length five
- Decomposing highly edge-connected graphs into paths of any given length
- Edge-decomposition of graphs into copies of a tree with four edges
- Star decomposition of graphs
- Packing seagulls
- Induced star partition of graphs
- Monochromatic \(K_{r}\)-decompositions of graphs
- Packing degenerate graphs
- Minimum \(H\)-decompositions of graphs
- Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
- On the Weisfeiler-Leman dimension of fractional packing
- Graph decomposition of slim graphs
- Edge-decompositions of highly connected graphs into paths
- A cube dismantling problem related to bootstrap percolation
- Minimalist designs
- Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
- Covering the edges of bipartite graphs using \(K_{2,2}\) graphs
- A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
- Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
- Edge decompositions into two kinds of graphs
- Constructive Packings of Triple Systems
- scientific article; zbMATH DE number 3961623 (Why is no real title available?)
- The existence and construction of \((K_{5}\setminus e)\)-designs of orders 27, 135, 162, and 216
- Smaller embeddings of partial \(k\)-star decompositions
- On the complexity of deciding whether the regular number is at most two
- Graph factors and factorization: 1985--2003: a survey
- Decomposing highly connected graphs into paths of length five
- Polynomial cases of graph decomposition: A complete solution of Holyer's problem
- Star covers and star partitions of double-split graphs
- Computer search for graceful labeling: a survey
- On star partition of split graphs
- Star covers and star partitions of cographs and butterfly-free graphs
- Algorithmic complexity of weakly semiregular partitioning and the representation number
This page was built for publication: Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376161)
