1-Planar graphs without 6-cycles are 6-choosable

2026/07/25 by Qingqin Wu, Yiqiao Wang
#math.CO

paper · pdf

Abstract

A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. A graph is k-degenerate if each of its subgraphs contains a vertex of degree at most k. It was known that every 1-planar graph is 8-choosable. In this paper, we show that every 1-planar graph without 6-cycles is 5-degenerate and hence 6-choosable.

Related

• Planar graphs without pairwise adjacent 3-,4-,5-, and 6-cycle are\n 4-choosable
• Some conditions on 5-cycles that make planar graphs 4-choosable
• Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles
• Class two 1-planar graphs with maximum degree six or seven
• Sufficient conditions on cycles that make planar graphs 4-choosable