2021/08/23 by Felsner, Stefan, Ueckerdt, Torsten, Wille, Kaja
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.09994
The queue-number of a poset is the queue-number of its cover graph viewed as a directed acyclic graph, i.e., when the vertex order must be a linear extension of the poset. Heath and Pemmaraju conjectured that every poset of width w has queue-number at most w. Recently, Alam et al. constructed posets of width w with queue-number w+1. Our contribution is a construction of posets with width w with queue-number Ω(w2). This asymptotically matches the known upper bound.