Regular behavior of the maximal hypergraph chromatic number

DOI10.1137/19M1281861zbMATH Open1444.05055arXiv1808.01482OpenAlexW3034387541MaRDI QIDQ3300758FDOQ3300758

Authors: Danila Cherkashin, F. V. Petrov 

Publication date: 30 July 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $m(n,r)$ denote the minimal number of edges in an $n$-uniform hypergraph which is not $r$-colorable. It is known that for a fixed $n$ one has [ c_n r^n < m(n,r) < C_n r^n. ] We prove that for any fixed $n$ the sequence $a_r:=m(n,r)/r^n$ has a limit, which was conjectured by Alon. We also prove the list colorings analogue of this statement.

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

Recommendations

• On \(r\)-chromatic hypergraphs
• Colorings of hypergraphs with large number of colors
• Colorings of hypergraphs with large number of colors
• Hypergraphs with high chromatic number
• Coloring uniform hypergraphs with few colors

zbMATH Keywords

subadditivityhypergraph coloringErdős-Hajnal problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• What we know and what we do not know about Turán numbers
• Probability and Computing
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Title not available (Why is that?)
• Colorings of hypergraphs with large number of colors
• Hypergraphs with high chromatic number
• On the chromatic number of set systems
• Greedy colorings of uniform hypergraphs
• Extremal problems in hypergraph colourings

Cited In (4)

• Erdős-Hajnal problem for \(H\)-free hypergraphs
• Hypergraphs with high chromatic number
• Estimate of the number of edges in subgraphs of a Johnson graph
• On the Erdős-Hajnal problem for 3-graphs

This page was built for publication: Regular behavior of the maximal hypergraph chromatic number

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