On the weak chromatic number of random hypergraphs
| Autor: | Dmitry A. Shabanov, Alexander N. Semenov |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Hypergraph
Mathematics::Combinatorics Applied Mathematics 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Vertex (geometry) Combinatorics Binomial distribution Computer Science::Discrete Mathematics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Chromatic scale Mathematics |
| Zdroj: | Discrete Applied Mathematics. 276:134-154 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.03.025 |
| Popis: | The paper deals with weak chromatic numbers of random hypergraphs. Recall that a vertex coloring is said to be j -proper for a hypergraph if every j + 1 vertices of any edge do not share a common color. The j -chromatic number of a hypergraph is the minimum number of colors required for a j -proper coloring. We study the j -chromatic number of a random hypergraph in the binomial model H ( n , k , p ) in the case j = k − 2 and investigate, for fixed r , the threshold for the property that ( k − 2 ) -chromatic number of H ( n , k , p ) does not exceed r . This threshold corresponds to the sparse case, when p = c n ∕ n k for a fixed parameter c > 0 and the main result gives the tight bounds for it. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect