2022/10/13 by Diane Castonguay, Castonguay, Diane, Erika M. M. Coelho +7
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2210.06714
openalex publication_date 2022/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In Partition Into Complementary Subgraphs (Comp-Sub) we are given a graph G=(V,E), and an edge set property Π, and asked whether G can be decomposed into two graphs, H and its complement H, for some graph H, in such a way that the edge cut [V(H),V(H)] satisfies the property Π. Motivated by previous work, we consider Comp-Sub(Π) when the property Π=PM specifies that the edge cut of the decomposition is a perfect matching. We prove that Comp-Sub(PM) is GI-hard when the graph G is \Ck≥ 7, Ck≥ 7 \-free. On the other hand, we show that Comp-Sub(PM) is polynomial-time solvable on hole-free graphs and on P5-free graphs. Furthermore, we present characterizations of Comp-Sub(PM) on chordal, distance-hereditary, and extended P4-laden graphs.