加载中…
We study -crossing-critical graphs, which are the minimal graphs that require at least edge-crossings when drawn in the plane. For every fixed pair of integers with and , we give first explicit constructions of -crossing-critical graphs containing a vertex of degree greater than . We also show that such unbounded degree constructions do not exist for , precisely, that there exists a constant such that every -crossing-critical graph with has maximum degree at most . Hence, the bounded maximum degree conjecture of -crossing-critical graphs, which was generally disproved in 2010 by Dvo\v{r}'ak and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values

生成讲解博客的中文版本

生成AI智能校验的中文版本