A characterization of some graph classes with no long holes
type: Item
instance of: scholarly article
title: A characterization of some graph classes with no long holes
zbMATH Open document ID: 0842.05074
author: Elaine M. Eschen
author: R. Sritharan
published in: Journal of Combinatorial Theory. Series B
publication date: 1996-07-28T00:00:00Z
review text: The authors' main result is in some way a generalization of the next two theorems. T1 (Dirac, 1961): \(G\) is a triangulated graph, iff each induced subgraph \(H\) of \(G\) is a clique or has two nonadjacent simplicial vertices of \(H\). T2 (Chvátal, Rusu, 1993): A graph contains no holes, iff each of its subgraphs \(H\) with at least one edge contains an edge that is not middle of any chordless path \(P_4\) on 4 vertices in \(H\). The authors study a hierarchy of graphs \(G\) without holes and without some antiholes (complements of holes). They receive the following theorem: A graph \(G\) on \(n\) vertices contains no holes and no antiholes with \(i\) vertices \((5\leq i\leq k+ 1\leq n)\), iff for every induced subgraph \(H\) of \(G\) with at least one edge, either \(H\) is inseparable and has at least \([\mu(H)/2]\) edges that are \(k\)-simplicial in \(H\), or \(H\) has two separable edges that are \(k\)-simplicial in \(H\). A graph \(H\) is inseparable if its any two edges with no common vertices belong to a path on 4 vertices in \(H\). The number \([\mu(H)/2]\) denotes the size of nontrivial connected component of a given inseparable induced subgraph \(H\) of \(G\). An edge in a graph \(G\) is \(k\)-simplicial if its vertices are not endpoints of a chordless path on \(k\) vertices in the complement of \(G\). The authors give also a corollary concerning chordal bipartite graphs.
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 798762
zbMATH Keywords: triangulated graph
zbMATH Keywords: simplicial vertices
zbMATH Keywords: holes
zbMATH Keywords: antiholes
zbMATH Keywords: separable edges
zbMATH Keywords: path
zbMATH Keywords: endpoints
zbMATH Keywords: chordless path
zbMATH Keywords: chordal bipartite graphs
MaRDI profile type: Publication
full work available at URL: jctb.1995.1048
OpenAlex ID: W2040005901
DOI: 10.1006/JCTB.1995.1048
description: scientific article; zbMATH DE number 798762