Hypergraphs with high chromatic number
Let f(k,s) denote the minimal number of edges of a k-uniform hypergraph whose chromatic number is at least s. In this paper a conjecture made by \textit{P. Erdős} and \textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 12, 87-123 (1961; Zbl 0201.328)] which asserts that for every fixed \(k\geq 2\), if \(s>s_ 0(k)\) then \(f(k,s)=\left( \begin{matrix} (s-1)(k-1)+1\\ k\end{matrix} \right)\) holds is disproved. The author also proves that for every fixed k f(k,s)\(=\Omega (s^ k)\) as \(s\to \infty\) and proposes the following conjecture: for every fixed k the limit \(\lim_{s\to \infty}f(k,s)/s^ k\) exists.
- Constructions of sparse uniform hypergraphs with high chromatic number
- On r-chromatic hypergraphs
- Regular behavior of the maximal hypergraph chromatic number
- The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
- A contribution to the chromatic theory of uniform hypergraphs
- On the chromatic number of finite systems of subsets
- Graph properties and hypergraph colourings
- Acyclic subgraphs with high chromatic number
- Chromatic numbers of algebraic hypergraphs
- On the Erdős-Hajnal problem for 3-graphs
- On the chromatic number of set systems
- On the problem of Erdős and Hajnal in the case of list colorings
- Conflict-free colourings of uniform hypergraphs with few edges
- Coloring H-free hypergraphs
- Constructions of sparse uniform hypergraphs with high chromatic number
- On proper colourings of hypergraphs using prescribed colours
- Random coloring method in the combinatorial problem of Erdős and Lovász
- On splittable colorings of graphs and hypergraphs
- Regular behavior of the maximal hypergraph chromatic number
- scientific article; zbMATH DE number 3898934 (Why is no real title available?)
- ON HYPERGRAPH COLOURINGS
- scientific article; zbMATH DE number 3708458 (Why is no real title available?)
- Dense uniform hypergraphs have high list chromatic number
- A general framework for hypergraph coloring
- Extremal problems in hypergraph colourings
- Minors in Graphs with High Chromatic Number
- Colorings of hypergraphs with large number of colors
- Colorings of hypergraphs with large number of colors
- On r-chromatic hypergraphs
- Note on polychromatic coloring of hereditary hypergraph families
- Improvement of the lower bound in the Erdös-Hajnal combinatorial problem
- Coloring non-uniform hypergraphs without short cycles
This page was built for publication: Hypergraphs with high chromatic number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086588)
