graph_partition_edges (662B)
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 11 Variant: partitioning the vertices, see [graph_partition] 12 13 Up: [computational_problem] on [graph]