Crossing-critical graphs with large maximum degree

DOI10.1016/J.JCTB.2009.11.003MaRDI QIDQ974468zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Bojan Mohar

Publication date 3 June 2010

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.1599

zbMATH Keywords

bandwidthcrossing numberedge crossingscrossing critical

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A conjecture of Richter and Salazar about graphs that are critical for a fixed crossing number $k$ is that they have bounded bandwidth. A weaker well-known conjecture of Richter is that their maximum degree is bounded in terms of $k$. In this note we disprove these conjectures for every $kge171$, by providing examples of $k$-crossing-critical graphs with arbitrarily large maximum degree.

Recommendations

• Stars and bonds in crossing-critical graphs
• Stars and Bonds in Crossing-Critical Graphs
• Crossing-number critical graphs have bounded path-width
• scientific article; zbMATH DE number 2084270
• Improvement on the crossing number of crossing-critical graphs

Cites work

• Crossing-number critical graphs have bounded path-width
• Embedding grids in surfaces
• Graph minors. V. Excluding a planar graph
• New infinite families of almost-planar crossing-critical graphs
• Research problems from the 5th Slovenian Conference (Bled, 2003)
• Unexpected behaviour of crossing sequences

Cited in

(16)

• On degree properties of crossing-critical families of graphs
• Infinite families of crossing-critical graphs with prescribed average degree and crossing number
• Stars and bonds in crossing-critical graphs
• New upper bounds for the crossing numbers of crossing-critical graphs
• On 13-crossing-critical graphs with arbitrarily large degrees
• On the Pseudolinear Crossing Number
• On 13-crossing-critical graphs with arbitrarily large degrees
• On Degree Properties of Crossing-Critical Families of Graphs
• Structure and generation of crossing-critical graphs
• Nested cycles in large triangulations and crossing-critical graphs
• Construction of crossing-critical graphs
• Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\)
• Crossing-number critical graphs have bounded path-width
• scientific article; zbMATH DE number 7559214 (Why is no real title available?)
• Improvement on the crossing number of crossing-critical graphs
• scientific article; zbMATH DE number 2084270 (Why is no real title available?)

This page was built for publication: Crossing-critical graphs with large maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974468)