graph_partition_edges (825B)
1 # Graph partition edges 2 3 Partitioning the edges of a [graph] into specified patterns 4 5 - [dyer1985complexity] [NP_hard] to partition into [connected] [subgraphs] of size 3 even in case of [planar_graphs], and other results 6 - [bulteau2016decomposing]: also in the case of [cubic_graphs] 7 - Partitioning into [P3] is in [PTIME], it can be done by reduction to [perfect_matching] 8 - Also discussed in [diwan2015p3] 9 - In fact for simple undirected graphs a solution always exist when the connected components have an even number of edges, see [diwan2017decomposing] 10 - partitioning into triangles: [directed_triangle_decomposition] 11 - partitioning into copies of a fixed graph: [Holyer's_conjecture] 12 13 Variant: partitioning the vertices, see [graph_partition] 14 15 Up: [computational_problem] on [graph] 16 17 Aliases: graph edge partition