A nice class for the vertex packing problem

DOI10.1016/S0166-218X(96)00114-XMaRDI QIDQ1363736zbMATH OpenOpenAlexFDO

Authors P. Bertolazzi, Caterina De Simone, A. Galluccio

Publication date 22 December 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

Homogeneous sets substitution vertex packing

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Review text

If \(v\) is a vertex of a graph \(G_2\), we can substitute a graph \(G_1\) for \(v\) by taking the vertex-disjoint union of \(G_1\) and \(G_2-v\), and adding an edge between every vertex of \(G_1\) and every vertex of \(G_2-v\) that was adjacent to \(v\). If \({\mathcal C}\) is a class of graphs, let \({\mathcal C}^*\) denote the smallest class of graphs containing \({\mathcal C}\) and closed under substitution. The authors call a class \({\mathcal C}\) of graphs nice if membership in the class can be certified in polynomial time. If \({\mathcal C}\) is a nice class of graphs and \(G\) is an arbitrary graph, consider the question `Does \(G\) belong to \({\mathcal C}^*\)?' The authors show that the preceding question can be answered in polynomial time whenever a forbidden subgraph characterization of \({\mathcal C}^*\) is known. The authors provide a forbidden subgraph characterization for \({\mathcal C}^*\) when \({\mathcal C}\) is the class of graphs that are claw-free or bipartite.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: A nice class for the vertex packing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363736)