Erd\H os--Hajnal problem for H-free hypergraphs

2022/07/12 by Danila Cherkashin, Cherkashin, Danila, Alexei Gordeev +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2207.05840

openalex publication_date 2022/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper deals with the minimum number m_H(r) of edges in an H-free graph with the chromatic number more than r. We show how bounds on Ramsey and Turán numbers imply bounds on m_H(r).

Related

• On the Erd\H os--Hajnal problem in the case of 3-graphs
• Coloring H-free Hypergraphs
• A new randomized algorithm for the Erdos--Hajnal problem
• Unavoidable hypergraphs
• Erdos-Hajnal-type theorems in hypergraphs