Strict 2-threshold graphs
type: Item
instance of: scholarly article
title: Strict 2-threshold graphs
zbMATH Open document ID: 0658.05063
DOI: 10.1016/0166-218X(88)90048-0
author: N. V. R. Mahadev
author: Uri N. Peled
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: A graph is a strict 2-threshold graph if its edge set can be partitioned into two threshold graphs \(T_ 1\) and \(T_ 2\) so that any triangle in G appears in either \(T_ 1\) or \(T_ 2\). The authors give a polynomial- time algorithm for determining when G is a strict 2-threshold graph.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4075127
zbMATH Keywords: triangles in graphs
zbMATH Keywords: 2-threshold graph
zbMATH Keywords: edge set
zbMATH Keywords: algorithm
reviewed by: R. G. Stanton
MaRDI profile type: Publication
cites work: Q4165164
cites work: Four classes of perfectly orderable graphs
cites work: Q3328583
cites work: Bithreshold Graphs
cites work: Q3318808
cites work: Some properties of 2-threshold graphs
cites work: Bipartite bithreshold graphs
cites work: On the notion of balance of a signed graph
cites work: Sufficient Conditions for Graphs to Have Threshold Number 2
cites work: The Complexity of the Partial Order Dimension Problem
full work available at URL: 0166-218x(88)90048-0
OpenAlex ID: W2092353941
description: scientific article; zbMATH DE number 4075127