The complexity of list edge-partitions for simple graphs

详细信息    查看全文

• 作者：Payam Valadkhan ^{pvaladkh@sfu.ca}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：61
• 期：Complete
• 页码：219-234
• 全文大小：1024 K
• 卷排序：61

文摘

Given a symmetric m×mm×m matrix MM with entries from the set {0,1,∗}{0,1,∗}, the MM-edge-partition problem asks whether the edges of a given graph can be partitioned into mm parts E0,E1⋯Em−1E0,E1⋯Em−1 such that any two distinct edges in (possibly equal) parts ViVi and VjVj have a common endpoint if M(i,j)=1M(i,j)=1, and no common endpoint if M(i,j)=0M(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 MM-partition problem introduced by Feder et al. Following the current trends, we prove some complexity results for the list version of the MM-edge-partition problem restricted to simple graphs.