HackerPapers

arXiv:2102.04994math.CO

Erdos-Hajnal for graphs with no 5-hole

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality at least |G|^c. We prove that this is true when H is a cycle of length five. We also prove several further results: for instance, that if C is a cycle and H is the complement of a forest, there exists c>0 such that every graph G containing neither of C,H as an induced subgraph has a clique or stable set of cardinality at least |G|^c.

arXiv comments
Journal reference
DOI
Subjects
math.COCombinatorics

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Apr 2021 to Apr 2021.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. New proof reveals that graphs with no pentagons are fundamentally different 1 comment

    • I'm impressed by how clear the article is for a layman. I only know the very basics of graph theory and Ramsay theory and I understood the topic perfectly. This is in comparison to the paper [1] which at a glance seems terse and difficult to understand. If anyone likes Ramsay…

      mFixmanView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.