Q5874491
type: Item
instance of: scholarly article
author: Édouard Bonnet
author: Xuan Thang Tran
author: Rémi Watrigant
author: Stéphan Thomassé
publication date: 2023-02-07T00:00:00Z
full work available at URL: https://arxiv.org/abs/2004.12166
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7651162
zbMATH Keywords: approximation
zbMATH Keywords: maximum independent set
zbMATH Keywords: \(H\)-free graphs
zbMATH Keywords: Erdő's-Hajnal conjecture
MaRDI profile type: Publication
cites work: A note on Ramsey numbers
cites work: Q4770411
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: Some APX-completeness results for cubic graphs
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Sparse graphs: Metrics and random models
cites work: Q5422499
cites work: Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
cites work: Polynomial-time approximation schemes for packing and piercing fat objects
cites work: Approximation algorithms for maximum independent set of pseudo-disks
cites work: The Erdős-Hajnal conjecture. A survey
cites work: Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
cites work: Ramsey-type theorems
cites work: Graph Theory and Probability. II
cites work: On the size of a random maximal graph
cites work: Some remarks on the theory of graphs
cites work: Q4198056
cites work: Geometric algorithms and combinatorial optimization
cites work: Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs
cites work: Q4886045
cites work: Q5875555
cites work: The Ramsey number R(3, t) has order of magnitude t2/log t
cites work: Bounding Ramsey numbers through large deviation inequalities
cites work: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Ramsey numbers and an approximation algorithm for the vertex cover problem
cites work: Computing independent sets in graphs with large girth
cites work: Improved results on geometric hitting set problems
cites work: Q3002782
DOI: 10.4230/LIPICS.ESA.2020.23
Recommended article: Q3424894
Recommended article: Q5167455
Recommended article: A Weakening of the Odd Hadwiger's Conjecture
Recommended article: The Erdős-Hajnal conjecture. A survey
Recommended article: Q3359497
Recommended article: Algorithmic aspects of Suslin's proof of Serre's conjecture
Recommended article: A survey and strengthening of Erdős-Gyarfas conjecture
Recommended article: A strengthening of the Erdős-Szekeres theorem
Recommended article: On Helly's theorem: Algorithms and extensions
Recommended article: An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound
description: scientific article; zbMATH DE number 7651162