Upper bound in the Erdős-Hajnal problem of hypergraph coloring

DOI10.1134/S0001434613010197MaRDI QIDQ1947784zbMATH OpenOpenAlexFDO

Authors S. M. Teplyakov

Publication date 26 April 2013

Published in Mathematical Notes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0001434613010197

zbMATH Keywords

hypergraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Review text

This paper deals with the quantity \(m_k (n)\), the least number of edges of an \(n\)-homogeneous hypergraph whose vertices cannot be two colored in such a way that every edge contains at least \(k\) vertices of each color class. The bound for \(m_ k(n)\) obtained in [\textit{D. A. Shabanov}, Izv. Math. 71, No. 6, 1253--1290 (2007); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 71, No. 6, 183--222 (2007; Zbl 1247.05116)] is obtained here under weaker assumptions on \(k\).

Recommendations

• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• An upper bound for total colouring of graphs
• Approximability of the upper chromatic number of hypergraphs
• A new upper bound for total colourings of graphs
• Extremal problems in hypergraph colourings
• Around Erdős-Lovász problem on colorings of non-uniform hypergraphs
• scientific article; zbMATH DE number 786134
• scientific article; zbMATH DE number 568840
• Extremal problems for colourings of uniform hypergraphs
• Upper bounds for the achromatic and coloring numbers of a graph

Cites work

• Color-critical graphs and hypergraphs with few edges: a survey
• Extremal problems for colourings of uniform hypergraphs
• On a property of families of sets
• On general two-colorings of uniform hypergraphs
• On one combinatorial problem of Erdös
• On two-colorings of hypergraphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(9)

• New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\)
• 2-colorings of hypergraphs with large girth
• On small \(n\)-uniform hypergraphs with positive discrepancy
• Combinatorial extremum problems for 2-colorings of hypergraphs
• On some generalizations of the property B problem of an \(n\)-uniform hypergraph
• On algorithmic methods of analysis of two-colorings of hypergraphs
• scientific article; zbMATH DE number 3335822 (Why is no real title available?)
• Colorings of hypergraphs with large number of colors
• Letter to the editor

This page was built for publication: Upper bound in the Erdős-Hajnal problem of hypergraph coloring

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