A new infinite family of 4-regular crossing-critical graphs

2024/04/15 by Zongpeng Ding, Yuanqiu Huang, Ding, Zongpeng +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2404.09434

openalex publication_date 2024/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph G is said to be crossing-critical if cr(G-e)< cr(G) for every edge e of G, where cr(G) is the crossing number of G. Richter and Thomassen [Journal of Combinatorial Theory, Series B 58 (1993), 217-224] constructed an infinite family of 4-regular crossing-critical graphs with crossing number 3. In this article, we present a new infinite family of 4-regular crossing-critical graphs.

Related

• New upper bounds for the crossing numbers of crossing-critical graphs
• Improvement on the crossing number of crossing-critical graphs
• Infinite families of crossing-critical graphs with prescribed average degree and crossing number
• Technical details regarding infinite families of crossing-critical graphs with prescribed average degree and crossing number
• Making a graph crossing-critical by multiplying its edges