2024/11/04 by Thérèse Biedl, Biedl, Therese, Prosenjit Bose +3
Computer Science · #05C10 #05C62 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2411.02686
openalex publication_date 2024/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The d-independence number of a graph G is the largest possible size of an independent set I in G where each vertex of I has degree at least d in G. Upper bounds for the d-independence number in planar graphs are well-known for d=3,4,5, and can in fact be matched with constructions that actually have minimum degree d. In this paper, we explore the same questions for 1-planar graphs, i.e., graphs that can be drawn in the plane with at most one crossing per edge. We give upper bounds for the d-independence number for all d. Then we give constructions that match the upper bound, and (for small d) also have minimum degree d.