Weakly triangulated graphs
type: Item
instance of: scholarly article
title: Weakly triangulated graphs
zbMATH Open document ID: 0551.05055
DOI: 10.1016/0095-8956(85)90050-4
author: Ryan Hayward
published in: Journal of Combinatorial Theory. Series B
publication date: 1985-01-01T00:00:00Z
review text: A graph is triangulated if it has no chordless cycle with four or more vertices. It follows that the complement of a triangulated graph cannot contain a chordless cycle with five or more vertices. We introduce a class of graphs (namely weakly triangulated graphs) which includes both triangulated graphs and complements of triangulated graphs (we define a graph as weakly triangulated if neither it nor its complement contains a chordless cycle with five or more vertices). Our main result is a structural theorem which leads to a proof that weakly triangulated graphs are perfect.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 3877233
zbMATH Keywords: perfect graphs
zbMATH Keywords: chordless cycle
zbMATH Keywords: triangulated graph
MaRDI profile type: Publication
full work available at URL: 0095-8956(85)90050-4
OpenAlex ID: W2082068582
Wikidata QID: Q56656644
cites work: Q3222875
cites work: Q3347930
cites work: Q3222224
cites work: Star-cutsets and perfect graphs
cites work: On rigid circuit graphs
cites work: Q3271426
cites work: A note on the semi-strong perfect graph conjecture
cites work: An algorithm for finding clique cut-sets
DBLP publication ID: journals/jct/Hayward85
description: scientific article; zbMATH DE number 3877233