A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2 (Q2488941): Difference between revisions
From MaRDI portal
Latest revision as of 14:03, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2 |
scientific article |
Statements
A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2 (English)
0 references
16 May 2006
0 references
The upper chromatic number \(\xi(\overline {{\mathcal H}})\) of a hypergraph \({\mathcal H}=(X,{\mathcal E})\) is the maximum number \(k\) for which there exists a partition of \(X\) into nonempty subsets \(X_{1}, X_{2}, X_{k}\) such that for each edge at least two vertices lie in one of the partite sets. We prove that for every \(n>3\) there exists a 3-uniform hypergraph with \(n\) vertices, upper chromatic number \(2\) and \(\frac{n(n-2)}{3}\) edges which implies that a corresponding bound proved by \textit{K. Diao, P. Zhao} and \textit{H. Zhou} [Discrete Math. 220, No.\,1-3, 67--73 (2000; Zbl 0949.05031)] is best-possible.
0 references