scientific article; zbMATH DE number 7651162

DOI10.4230/LIPICS.ESA.2020.23MaRDI QIDQ5874491zbMATH OpenFDO

Authors Édouard Bonnet, Xuan Thang Tran, Rémi Watrigant, Stéphan Thomassé

Publication date 7 February 2023

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

zbMATH Keywords

\(H\)-free graphsapproximationErdő's-Hajnal conjecturemaximum independent set

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• scientific article; zbMATH DE number 5130830
• On Erdös-Gallai and Havel-Hakimi algorithms
• A Weakening of the Odd Hadwiger's Conjecture
• The Erdős-Hajnal conjecture. A survey
• scientific article; zbMATH DE number 4213130
• Algorithmic aspects of Suslin's proof of Serre's conjecture
• A survey and strengthening of Erdős-Gyarfas conjecture
• A strengthening of the Erdős-Szekeres theorem
• On Helly's theorem: Algorithms and extensions
• An algorithm for Komlós conjecture matching Banaszczyk's bound

Cites work

• A note on Ramsey numbers
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for NP-complete problems on planar graphs
• Bounding Ramsey numbers through large deviation inequalities
• Computing independent sets in graphs with large girth
• Geometric algorithms and combinatorial optimization
• Graph theory
• Graph Theory and Probability. II
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• scientific article; zbMATH DE number 7650229 (Why is no real title available?)
• Improved results on geometric hitting set problems
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum weight independent set for claw-free graphs in polynomial time
• On maximal independent sets of vertices in claw-free graphs
• On the size of a random maximal graph
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Ramsey-type theorems
• Some APX-completeness results for cubic graphs
• Some remarks on the theory of graphs
• Sparse graphs: metrics and random models
• The Erdős-Hajnal conjecture. A survey
• The Ramsey number R(3, t) has order of magnitude t²/log t

Cited in

(8)

• A lower bound for weak Schur numbers with a deterministic algorithm
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• Algorithmic aspects of Suslin's proof of Serre's conjecture
• scientific article; zbMATH DE number 5130830 (Why is no real title available?)
• A Weakening of the Odd Hadwiger's Conjecture
• scientific article; zbMATH DE number 6450652 (Why is no real title available?)
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
• Parameterized inapproximability of independent set in \(H\)-free graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874491)