A $c$-crossing-critical graph is one that has crossing number at least $c$ but each of its proper subgraphs has crossing number less than $c$. Recently, a set of explicit construction rules was identified by Bokal, Oporowski, Richter, and Salazar to generate all large $2$-crossing-critical graphs (i.e., all apart from a finite set of small sporadic graphs). They share the property of containing a generalized Wagner graph $V_{10}$ as a subdivision. In this paper, we study these graphs and establish their order, simple crossing number, edge cover number, clique number, maximum degree, chromatic number, chromatic index, and treewidth. We also show that the graphs are linear-time recognizable and that all our proofs lead to efficient algorithms for the above measures.
翻译：以美元为单位的交叉关键图形是一个至少超过1美元(c)的图形,但每个正确的子集的交叉数字都低于1美元(c)。 最近,Bokal、Oporowski、Richter和Salazar确定了一套明确的建筑规则,以生成所有大型的2美元交叉关键图形(即,除一组有限的小零星图形外,所有这些图形都具有共同的属性,它们包含一个通用的Wagner图形 $V ⁇ 10}($V ⁇ 10}), 作为分层。在本文中,我们研究了这些图表,并确定了它们的顺序、简单交叉号、边缘覆盖号、区号、最大度、染色号、色体索引和树线。我们还显示这些图表是线性时间可识别的,我们的所有证据都导致上述措施的有效算法。
相关内容
微信扫码咨询专知VIP会员