Forbidden subgraph decomposition
type: Item
instance of: scholarly article
title: Forbidden subgraph decomposition
zbMATH Open document ID: 0994.05122
DOI: 10.1016/S0012-365X(01)00173-X
author: Irena Rusu
author: Jeremy P. Spinrad
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: Let \(F=(X,Y)\) be a bipartite graph with bipartite sets \(X\) and \(Y\). Given a graph \(G=(V,E)\) and a partitition \(P = V_1 \cup V_2\) of its vertices, let \(G_P = (V,E*)\) be the graph with edges consisting of all those edges in \(G\) with one vertex in \(V_1\) and the other in \(V_2\). We say \(F\) is tidily induced in \(G_P\) if there exists an isomorphism \(f\) from \(F\) to an induced subgraph \(H\) of \(G_P\) so that \(f(x) \in V_1\) for all \(x \in X\) and \(f(y) \in V_2\) for all \(y \in Y\). We say \(P\) is an \(F\)-free decomposition of \(G\) if \(|V_1|\geq |X|\), \(|V_2|\geq |Y|\) and \(F\) is not tidily induced in \(G_P\). The authors study the complexity of recognising \(F\)-free decompositions for small \(F\), in particular bipartite graphs with at most 4 vertices. The main result is that deciding whether a graph has a \(2K_2\)-free decomposition is NP-complete.
reviewed by: Katherine Heinrich
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1746235
zbMATH Keywords: graph decomposition
zbMATH Keywords: complexity
zbMATH Keywords: bipartite graph
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00173-x
OpenAlex ID: W2017867718
Recommended article: Forbidden subgraphs and graph decomposition
Recommended article: Forbidden subgraphs and forbidden substructures
Recommended article: Forbidden induced subgraphs
Recommended article: Forbidden subgraphs in connected graphs
Recommended article: Q3826590
Recommended article: Splits with forbidden subgraphs
Recommended article: Q3971999
Recommended article: Q4326211
Recommended article: Q3838206
Recommended article: Forbidden subgraphs of power graphs
description: scientific article; zbMATH DE number 1746235