On a conjecture concerning 4-coloring of graphs with one crossing

2025/04/11 by Dvořák, Zdeněk, Lidický, Bernard, Mohar, Bojan
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.08327

Abstract

We conjecture that every graph of minimum degree five with no separating triangles and drawn in the plane with one crossing is 4-colorable. In this paper, we use computer enumeration to show that this conjecture holds for all graphs with at most 28 vertices, explore the consequences of this conjecture and provide some insights on how it could be proved.

Related

• Coloring graphs with crossings
• Coloring plane graphs with independent crossings
• A formal proof of the four color theorem
• Mathematical Proofs of Two Conjectures: The Four Color Problem and The Uniquely 4-colorable Planar Graph
• (2P₂,K₄)-Free Graphs are 4-Colorable