Extension of hereditary classes with substitutions
type: Item
instance of: scholarly article
title: Extension of hereditary classes with substitutions
zbMATH Open document ID: 1021.05095
DOI: 10.1016/S0166-218X(02)00507-3
published in: Discrete Applied Mathematics
publication date: 2003-06-10T00:00:00Z
review text: A substitution of graph \(H\) in graph \(G\) instead of a vertex \(v\in V(G)\) is the graph consisting of the disjoint union of \(H\) and \(G-v\) with additional edge-set \(\{xy\mid x\in V(H)\) and \(y\in N_G(v)\}\), where \(N_G(v)= N(x)\) of all vertices \(v\) in \(G\) adjacent to \(x\). For a class \({\mathcal P}\) of graphs, its substitutional closure \({\mathcal P}^*\) consists of all graphs that can be obtained from \({\mathcal P}\) by repeated substitutions. Let \(\text{ISub}(G)\) be the set of all induced subgraphs of a graph \(G\). A class of graphs \({\mathcal P}\) is called hereditary if \(\text{ISUB}(G)\subseteq{\mathcal P}\) for every \(G\in{\mathcal P}\). A graph \(F\) is a minimal forbidden induced subgraph for a hereditary class \({\mathcal P}\) if \(\text{ISub}(F)\setminus{\mathcal P}= \{F\}\). The author proposes a method of constructing forbidden induced subgraphs for \({\mathcal P}^*\).
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 1925301
zbMATH Keywords: hereditary class of graphs
zbMATH Keywords: homogeneous set
zbMATH Keywords: substitutional closure
zbMATH Keywords: stability number
author: I.È. Zverovich
MaRDI profile type: Publication
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: A nice class for the vertex packing problem
cites work: On the vertex packing problem
cites work: Q4193514
cites work: Transitiv orientierbare Graphen
cites work: Some classes of perfectly orderable graphs
cites work: A translation of Gallai's paper: `Transitiv orientierbare Graphen'
cites work: On the closure of triangle-free graphs under substitution
cites work: Weak bipolarizable graphs
cites work: Q4871056
cites work: A finiteness theorem for primal extensions
cites work: Strong k-colourings of graphs
full work available at URL: s0166-218x(02)00507-3
OpenAlex ID: W2089857777
description: scientific article; zbMATH DE number 1925301