\(r\)-bounded \(k\)-complete bipartite bihypergraphs and generalized split graphs
type: Item
instance of: scholarly article
title: \(r\)-bounded \(k\)-complete bipartite bihypergraphs and generalized split graphs
zbMATH Open document ID: 1010.05047
DOI: 10.1016/S0012-365X(01)00318-1
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: The set of all induced subgraphs of a graph \(G\) will be denoted by \(\text{ISub}(G)\). A class \(\mathbb{P}\) of graphs is called hereditary if \(\text{ISub}(G)\subseteq\mathbb{P}\) for all \(G\in \mathbb{P}\). Let \(Z\) be a set of graphs, and set \(\text{FIS}(Z)= \{G\mid \text{ISub}(G)\cap Z=\varnothing\}\). We say that a class \(\mathbb{P}\) is finitely generated if \(\mathbb{P}= \text{FIS}(Z)\) for a finite set \(Z\). A class \(\mathbb{P}\) of graphs is called \(\alpha\)-bounded (resp. \(\omega\)-bounded) if there exists a constant \(c\) such that \(\alpha(G)\leq c\) (resp. \(\omega(G)\leq c\)) for all \(G\in\mathbb{P}\). The \((\alpha,\beta)\)-polar graphs are a generalization of the split graphs (the class of split graphs coincides with the class of \((1,1)\)-polar graphs). The main result of this article shows that every class of \((\alpha,\beta)\)-polar graphs has a finite FIS-characterization. This result generalizes some well-known results about this type of graph.
reviewed by: Alain Bretto
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 1746246
author: I.È. Zverovich
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00318-1
OpenAlex ID: W1979914260
description: scientific article; zbMATH DE number 1746246