This is the authors' abstract. We don't add key points for this paper.
We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju asserts that every poset of width w has queue number at most w . The conjecture has been confirmed for posets of width $$w=2$$ w = 2 via so-called lazy linear extension. We extend and thoroughly analyze lazy linear extensions for posets of width $$w > 2$$ w > 2 . Our analysis implies an upper bound of (w-1)² +1 ( w - 1 ) 2 + 1 on the queue number of width- w posets, which is tight for the strategy and yields an improvement over the previously best-known bound. Further, we provide an example of a poset that requires at least $$w+1$$ w + 1 queues in every linear extension, thereby disproving the conjecture for posets of width $$w > 2$$ w > 2 .
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Alam et al. (2022) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: