Erdős-Hajnal problem for H-free hypergraphs

DOI10.1007/S00373-023-02737-6arXiv2207.05840OpenAlexW4390298191MaRDI QIDQ6144501FDOQ6144501

Authors: Danila Cherkashin, Alexey Gordeev, Georgii Strukov 

Publication date: 29 January 2024

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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'an numbers imply bounds on $m_H(r)$.

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

Recommendations

• On the Erdős-Hajnal problem for 3-uniform hypergraphs
• Lower bounds for the number of edges in hypergraphs of certain classes
• On the Erdős-Hajnal problem for 3-graphs
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Improvement of the lower bound in the Erdös-Hajnal combinatorial problem

zbMATH Keywords

Ramsey theoryhypergraph colorings\(H\)-free graphsTurán numbers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Cites Work

• Coloring \(H\)-free hypergraphs
• Hypergraph Ramsey numbers
• On the chromatic number of set systems
• Greedy colorings of uniform hypergraphs
• Trees in greedy colorings of hypergraphs
• On the Erdős-Hajnal problem for 3-graphs
• Extremal problems in hypergraph colourings
• Independent sets in hypergraphs with a forbidden link
• Regular behavior of the maximal hypergraph chromatic number
• Hypergraph Ramsey numbers: triangles versus cliques

This page was built for publication: Erdős-Hajnal problem for \(H\)-free hypergraphs

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