A graph \(G\) has a decomposition into graphs \(G_1,\dots,G_t\), if \(G\) is an edge-disjoint union of graphs each of which is isomorphic to some graph \(G_i\). Let \(c\) be a fixed positive integer. The main result of the paper states that the problem to decide whether a graph \(G\) has an edge decompositions into graphs \(K_{1,c}\) and \(cK_2\) (the only two \(\Delta\)-systems of size \(c\) in the case of graphs) is in the class P.
Recommendations
Cites work
- A note on the decomposition of graphs into isomorphic matchings
- Decomposition of large uniform hypergraphs
- Decompositions of partially ordered sets into chains and antichains of given size
- scientific article; zbMATH DE number 3974987 (Why is no real title available?)
- Intersection Theorems for Systems of Sets
- NP-completeness of graph decomposition problems
- Packing, covering and decomposing of a complete uniform hypergraph into delta-systems
Cited in
(7)- Edge decompositions into two kinds of graphs
- Decomposition of the complete hypergraph into delta-systems. I
- Clique and anticlique partitions of graphs
- Edge decompositions and rooted packings of graphs
- scientific article; zbMATH DE number 125474 (Why is no real title available?)
- Delta-systems and qualitative (in)dependence
- Clique and anticlique partitions of graphs
This page was built for publication: Delta-system decompositions of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356709)
