关于平面图队列数的技术咨询

嘿，针对你提出的「有没有已知队列数大于2的平面图」这个问题，我整理了当前相关的研究情况和已知信息：

首先先明确下队列数的定义：它指的是将图的边划分成最少数量的子集，使得在某个顶点排序下，每个子集里都不存在嵌套边对——换句话说，如果在排序里四个顶点满足 (a < b < c < d)，且边 (ad) 和 (bc) 都存在的话，这两条边必须分到不同的子集里。

已知的上界情况 #

• 2019年，Dujmović等人证明了所有平面图的队列数至多为49；
• 2021年，Bekos等人将这个上界改进到了42。

已知的下界情况 #

目前已知的平面图中，队列数最大的是2。比如有6个顶点、9条边的3-sun图，它的队列数就是2。而且在2013年Battista等人的论文里就提到过：

似乎还没有已知平面图队列数的下界大于2

对你问题的直接回答 #

1. 目前已知的平面图中，最高的队列数确实是2；
2. 至于「所有平面图的队列数是否都不超过2」这个猜想，现在还没有定论。虽然现有上界是42，但有没有可能把这个上界收紧到2，还需要后续的研究来验证，目前来看是有探讨空间的，但还没有确凿的结论。

备注：内容来源于stack exchange，提问作者izzyg