A bound for the Dilworth number
type: Item
instance of: scholarly article
title: A bound for the Dilworth number
zbMATH Open document ID: 0732.05036
DOI: 10.1016/0012-365X(90)90153-9
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: Finite, undirected graphs \(G=(V,E)\) without loops or multiple edges were considered. For the Dilworth number \(\nabla (G)\) (the cardinality of the maximum size antichains; \textit{R. P. Dilworth} [Ann. Math. Ser. 2, 51, 161-166 (1950; Zbl 0038.020)]) of such a nontrivial simple graph with rank r(G) the inequality \[ \nabla (G)\leq 2r(G)-1 \] was derived. The rank r(G) is the rank of the adjacency matrix of G. In the case of \(\nabla\) odd it holds \[ \nabla (G)\leq 2[r(G)-1]-1. \]
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 4210176
author: Cyriel Van Nuffelen
author: M. Van Wouwe
MaRDI profile type: Publication
cites work: Q5615282
cites work: A decomposition theorem for partially ordered sets
cites work: The Dilworth Number of a Graph
cites work: Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
cites work: `` Strong '' NP-Completeness Results
cites work: Q4055645
cites work: The structure of Sperner k-families
cites work: On partitions of a partially ordered set
cites work: On Dilworth's theorem in the infinite case
cites work: A Note on Dilworth's Embedding Theorem
cites work: On Dilworth's decomposition theorem for partially ordered sets
cites work: Q4196460
full work available at URL: 0012-365x(90)90153-9
OpenAlex ID: W2046245502
description: scientific article; zbMATH DE number 4210176