Crossing-critical graphs with large maximum degree (Q974468): Difference between revisions

The crossing number of a graph is the fewest number of edge-crossings over all planar drawings. The graph is \(k\)-crossing-critical if its crossing number is at least \(k\) and deleting any edge lowers the crossing number. Label the vertices \(v_i\) of a graph by distinct integers \(f(v_i)\) and consider \(\max | f(v_i)-f(v_j)|\) over all edges \(v_i v_j\). The bandwidth is the smallest such maximum taken over all labelings. Richter and Salazar conjectured that any \(k\)-crossing-critical graph has its bandwidth bounded in terms of \(k\). A weaker conjecture of Richter says that its maximum degree is bounded in terms of \(k\). In this note the authors disprove these conjectures for every \(k \geq 171\) by providing examples of \(k\)-crossing-critical graphs with arbitrarily large maximum degree.