DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2024.13

On the Independence Number of 1-Planar Graphs

Authors: Therese Biedl, Prosenjit Bose, and Babak Miraftab

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

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.

Cite as

Therese Biedl, Prosenjit Bose, and Babak Miraftab. On the Independence Number of 1-Planar Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SWAT.2024.13,
  author =	{Biedl, Therese and Bose, Prosenjit and Miraftab, Babak},
  title =	{{On the Independence Number of 1-Planar Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.13},
  URN =		{urn:nbn:de:0030-drops-200537},
  doi =		{10.4230/LIPIcs.SWAT.2024.13},
  annote =	{Keywords: 1-planar graph, independent set, minimum degree}
}

Search Results

Documents authored by Miraftab, Babak

On the Independence Number of 1-Planar Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message