论文标题
带有有限树宽的图形的本地队列数
The Local Queue Number of Graphs with Bounded Treewidth
论文作者
论文摘要
图$ g $的队列布局由$ g $的顶点订购以及将边缘分配到所谓的队列中，使得在同一队列巢中没有两个边，即在abba-pattern中订购了端点。继续对本地订购的覆盖号码进行研究，我们将图$ g $的本地队列数字介绍为最低$ \ ell $，以便$ g $允许每个顶点的队列布局，每个顶点的事件边缘不超过$ \ ell $ queues。与本地页码[Merker，Ueckerdt，GD'19]类似，本地队列号与图形密度密切相关，并且可以任意远离经典队列号。 我们提供工具，以限制上方和下方的本地队列数量的图形，重点是TreeWidth $ K $的图。使用这些，我们表明每张treewidth $ k $的图最多都有本地队列编号，最多$ k+1 $，而这种限制为$ k = 2 $，而一般下限为$ \ lceil k/2 \ rceil+1 $。除其他外，我们的结果表明，平面图中的最大局部队列数为3或4。
A queue layout of a graph $G$ consists of a vertex ordering of $G$ and a partition of the edges into so-called queues such that no two edges in the same queue nest, i.e., have their endpoints ordered in an ABBA-pattern. Continuing the research on local ordered covering numbers, we introduce the local queue number of a graph $G$ as the minimum $\ell$ such that $G$ admits a queue layout with each vertex having incident edges in no more than $\ell$ queues. Similarly to the local page number [Merker, Ueckerdt, GD'19], the local queue number is closely related to the graph's density and can be arbitrarily far from the classical queue number. We present tools to bound the local queue number of graphs from above and below, focusing on graphs of treewidth $k$. Using these, we show that every graph of treewidth $k$ has local queue number at most $k+1$ and that this bound is tight for $k=2$, while a general lower bound is $\lceil k/2\rceil+1$. Our results imply, inter alia, that the maximum local queue number among planar graphs is either 3 or 4.
