A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs
It is well known that the chromatic number of a graph cannot exceed its maximum degree plus one. In the case of \(k\)-uniform hypergraphs, it is known that there exists an \(r\)-coloring if the maximum degree does not exceed an expression depending on \(k\) and \(r\). There is also a known upper bound for the maximum degree of \(k\)-uniform hypergraphs that guarantees the existence of an \(r\)-equitable coloring. In this paper, the author improves the known upper bound for the maximum degree that guarantees that a \(k\)-hypergraph has a 2-equitable coloring.
- A fast algorithm for equitable coloring
- A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
- An Ore-type theorem on equitable coloring
- Improved bounds and algorithms for hypergraph 2-coloring
- Random coloring method in the combinatorial problem of Erdős and Lovász
- The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- An Erdős-Gallai type theorem for uniform hypergraphs
- Strictly balanced uniform hypergraphs and generalizations of zero-one law
- Generating functions of some families of directed uniform hypergraphs
- On Motzkin-Straus type results for non-uniform hypergraphs
- On a generalisation of Mantel’s Theorem to Uniformly Dense Hypergraphs
- A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
- Defective colorings on k-uniform hypergraphs
- Equitable hypergraph orientations
This page was built for publication: A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353014)
