Fibres and ordered set coloring

Dwight Duffus; Henry Kierstead; W. T. Trotter

doi:10.1016/0097-3165(91)90083-S

Fibres and ordered set coloring

Dwight Duffus, Henry Kierstead, W. T. Trotter

Mathematical and Statistical Sciences, School of (SoMSS)

Research output: Contribution to journal › Article › peer-review

35 Scopus citations

Abstract

A fibre F of a partially ordered set P is a subset which intersects each nontrivial maximal antichain of P. Let λ be the smallest constant such that each finite partially ordered set P contains a fibre of size at most λ |P|. We show that λ \ ̌ 2 3 by finding a good 3-coloring of the nontrivial antichains of P. Some decision problems involving fibres are also considered. For instance, it is shown that the problem of deciding if a partially ordered set has a fibre of size at most κ is NP-hard.

Original language	English (US)
Pages (from-to)	158-164
Number of pages	7
Journal	Journal of Combinatorial Theory, Series A
Volume	58
Issue number	1
DOIs	https://doi.org/10.1016/0097-3165(91)90083-S
State	Published - Sep 1991

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0097-3165(91)90083-S

Cite this

@article{3d0ec4a168894fa8909d0a065b0059d0,

title = "Fibres and ordered set coloring",

abstract = "A fibre F of a partially ordered set P is a subset which intersects each nontrivial maximal antichain of P. Let λ be the smallest constant such that each finite partially ordered set P contains a fibre of size at most λ |P|. We show that λ \{\v } 2 3 by finding a good 3-coloring of the nontrivial antichains of P. Some decision problems involving fibres are also considered. For instance, it is shown that the problem of deciding if a partially ordered set has a fibre of size at most κ is NP-hard.",

author = "Dwight Duffus and Henry Kierstead and Trotter, {W. T.}",

note = "Funding Information: Contract N00014-85K-0769. Contract NO001485K-0494. Grant DMS 8942481.",

year = "1991",

month = sep,

doi = "10.1016/0097-3165(91)90083-S",

language = "English (US)",

volume = "58",

pages = "158--164",

journal = "Journal of Combinatorial Theory, Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Fibres and ordered set coloring

AU - Duffus, Dwight

AU - Kierstead, Henry

AU - Trotter, W. T.

N1 - Funding Information: Contract N00014-85K-0769. Contract NO001485K-0494. Grant DMS 8942481.

PY - 1991/9

Y1 - 1991/9

N2 - A fibre F of a partially ordered set P is a subset which intersects each nontrivial maximal antichain of P. Let λ be the smallest constant such that each finite partially ordered set P contains a fibre of size at most λ |P|. We show that λ \ ̌ 2 3 by finding a good 3-coloring of the nontrivial antichains of P. Some decision problems involving fibres are also considered. For instance, it is shown that the problem of deciding if a partially ordered set has a fibre of size at most κ is NP-hard.

AB - A fibre F of a partially ordered set P is a subset which intersects each nontrivial maximal antichain of P. Let λ be the smallest constant such that each finite partially ordered set P contains a fibre of size at most λ |P|. We show that λ \ ̌ 2 3 by finding a good 3-coloring of the nontrivial antichains of P. Some decision problems involving fibres are also considered. For instance, it is shown that the problem of deciding if a partially ordered set has a fibre of size at most κ is NP-hard.

UR - http://www.scopus.com/inward/record.url?scp=0041372118&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041372118&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(91)90083-S

DO - 10.1016/0097-3165(91)90083-S

M3 - Article

AN - SCOPUS:0041372118

SN - 0097-3165

VL - 58

SP - 158

EP - 164

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 1

ER -

Fibres and ordered set coloring

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this