2026-09-21T06:45:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20053 2026-09-05T16:28:32Z ddc:004 open_access

On the Independence Number of 1-Planar Graphs Biedl, Therese Bose, Prosenjit Miraftab, Babak 1-planar graph independent set minimum degree An independent set in a graph is a set of vertices where no two vertices are adjacent to each other. A maximum independent set is the largest possible independent set that can be formed within a given graph G. The cardinality of this set is referred to as the independence number of G. This paper investigates the independence number of 1-planar graphs, a subclass of graphs defined by drawings in the Euclidean plane where each edge can have at most one crossing point. Borodin establishes a tight upper bound of six for the chromatic number of every 1-planar graph G, leading to a corresponding lower bound of n/6 for the independence number, where n is the number of vertices of G. In contrast, the upper bound for the independence number in 1-planar graphs is less studied. This paper addresses this gap by presenting upper bounds based on the minimum degree δ. A comprehensive table summarizes these upper bounds for various δ values, providing insights into achievable independence numbers under different conditions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Therese Biedl and Prosenjit Bose and Babak Miraftab 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.13 urn:nbn:de:0030-drops-200537 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.13 eng https://creativecommons.org/licenses/by/4.0/legalcode