On the chromatic number of simple triangle-free triple systems (Q1010856)
From MaRDI portal
scientific article; zbMATH DE number 6106434
- Colorings of uniform hypergraphs with large girth
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the chromatic number of simple triangle-free triple systems |
scientific article; zbMATH DE number 6106434 |
|
Statements
On the chromatic number of simple triangle-free triple systems (English)
0 references
Colorings of uniform hypergraphs with large girth (English)
0 references
7 April 2009
0 references
15 November 2012
0 references
Summary: A hypergraph is simple if every two edges share at most one vertex. It is triangle-free if in addition every three pairwise intersecting edges have a vertex in common. We prove that there is an absolute constant \(c\) such that the chromatic number of a simple triangle-free triple system with maximum degree \(\Delta\) is at most \(c\sqrt{\Delta/\log \Delta}\). This extends a result of Johansson about graphs, and is sharp apart from the constant \(c\).
0 references
hypergraph
0 references
chromatic number
0 references
triangle free triple system
0 references
uniform hypergraph coloring
0 references
