PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS

摘要

Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V_1,V_2,... ,V_k) of V(G) such that for each i(1 ≤ i ≤ k) ,G[V] is 1-regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows : Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP-complete; induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.