Navigation

Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Göring, Frank; Harant, Jochen; Rautenbach, Dieter; Schiermeyer, Ingo : Locally Dense Independent Sets in Regular Graphs of Large Girth

Göring, Frank ; Harant, Jochen ; Rautenbach, Dieter ; Schiermeyer, Ingo : Locally Dense Independent Sets in Regular Graphs of Large Girth


Author(s):
Göring, Frank
Harant, Jochen
Rautenbach, Dieter
Schiermeyer, Ingo
Title:
Locally Dense Independent Sets in Regular Graphs of Large Girth
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 19, 2007
Mathematics Subject Classification:
05C69 [ Dominating sets, independent sets, cliques ]
Abstract:
For an integer $d\geq 3$ let $\alpha(d)$ be the supremum over all $\alpha$ with the property that for every $\epsilon>0$ there exists some $g(\epsilon)$ such that every $d$-regular graph of order $n$ and girth at least $g(\epsilon)$ has an independent set of cardinality at least $(\alpha-\epsilon)n$. Extending an approach proposed by Lauer and Wormald (Large independent sets in regular graphs of large girth, {\it J. Comb. Theory, Ser. B} {\bf 97} (2007), 999-1009) and improving results due to Shearer (A note on the independence number of triangle-free graphs, II, {\it J. Comb. Theory, Ser. B} {\bf 53} (1991), 300-307) and Lauer and Wormald, we present the best known lower bounds for $\alpha(d)$ for all $d\geq 3$.
Keywords:
independence, regular graph, probabilistic method, girth, randomized algorithm
Language:
English
Publication time:
10 / 2007

Presseartikel

  • Mehr Mathe dank Diplom

    TU Chemnitz bietet ab dem kommendem Wintersemester den modularisierten Diplomstudiengang Mathematik an …

  • „In Chemnitz ist sehr viel passiert“

    Im Podcast erzählt Prof. Martin Stoll, welche Serien er auf Netflix schaut, was ihn an Oxford fasziniert und wie es sich anfühlt, nach zwölf Jahren als Professor nach Chemnitz zurückzukehren …

  • MINT gewinnt

    Drei sächsische Hochschulen verfolgen unterschiedliche Konzepte, um Studieninteressenten Mathematik, Informatik, Naturwissenschaften und Technik schmackhaft zu machen …

  • Mathematik ganz alltagsnah

    „Videowoche der Mathematik“ zeigt das Fach von seiner spannenden, menschlichen und alltagstauglichen Seite …