Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903665 | European Journal of Combinatorics | 2017 | 16 Pages |
Abstract
Given a symmetric mÃm matrix M with entries from the set {0,1,â}, the M-edge-partition problem asks whether the edges of a given graph can be partitioned into m parts E0,E1â¯Emâ1 such that any two distinct edges in (possibly equal) parts Vi and Vj have a common endpoint if M(i,j)=1, and no common endpoint if M(i,j)=0. This problem generalizes some well-known edge-partition problems (such as the edge-coloring problem), and is in close relation with the well-known M-partition problem introduced by Feder et al. Following the current trends, we prove some complexity results for the list version of the M-edge-partition problem restricted to simple graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Payam Valadkhan,