Multi-intersection graphs
type: Item
instance of: scholarly article
title: Multi-intersection graphs
zbMATH Open document ID: 0945.05049
DOI: 10.1016/S0012-365X(99)00306-4
published in: Discrete Mathematics
publication date: 2000-09-27T00:00:00Z
review text: Multi-intersection graphs are defined as a generalization of intersection graphs. Vertices of a multi-intersection graph correspond to sets in a multi-family of sets (some sets in a multi-family may be repeated). Two vertices are adjacent if the corresponding sets have nonempty intersection. A class of graphs \(P\) is called hereditary if it is closed according to induced subgraphs. Suppose that \(P\) be a hereditary class of intersection graphs. \(P^{m}\) denote the class of multi-intersection graphs with the same family of subsets and multiplicity of each set at most \(m\). It is possible to characterize a hereditary class \(P\) in terms of forbidden induced subgraphs. There exists a class \(Z\) of graphs such that \(G\) is in \(P\) if and only if no induced subgraph of \(G\) is isomorphic to any graph in \(Z\). The author solves the problem of constructing the class of forbidden graphs \(Z\left( m\right)\) for the class \(P^{m}\). The class \(P\) and the corresponding class of forbidden graphs \(Z\) are given. This method is applied to the line graph of a multigraph and the class of the forbidden subgraphs is obtained.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 1453332
zbMATH Keywords: intersection graphs
zbMATH Keywords: hereditary properties
zbMATH Keywords: forbidden subgraphs
author: I.È. Zverovich
reviewed by: Ludovit Niepel
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1453332