Independent sets near the lower bound in bounded degree graphs

DOI10.4230/LIPICS.STACS.2017.28zbMath1402.05164arXiv1609.09134MaRDI QIDQ4636626

Bernard Lidický, Zdeněk Dvořák

Publication date: 19 April 2018

Full work available at URL: https://arxiv.org/abs/1609.09134

zbMATH Keywords

independent setfixed parameter tractabilitybounded degree\(\Delta\)-colorable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Turán’s Theorem Through Algorithmic Lens ⋮ Maximum independent sets near the upper bound

This page was built for publication: Independent sets near the lower bound in bounded degree graphs