## The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degree

### Authors:

- Edyta Barbara Szymańska

### Abstract

In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c (|V (H)|^{-1}/r-1); or minimum degree of a pair of vertices at least c (|V (H)|^{-2}/r-2) , has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain the first optimal dichotomy results for 2-colorings of r-uniform hypergraphs. For each problem and each r ≥ 3; we determine a threshold value depending on r such that the problem is NP-complete for c below the threshold, while for c strictly above the threshold it is polynomial. We provide an algorithm constructing the coloring with time complexity O(n^{C}); for some C = C(c; r) > 0: This algorithm becomes more efficient in cases r = 3; 4; 5 due to known Turán numbers of the triangle and the Fano plane. In addition, we determine the computational complexity of strong coloring of 3-uniform hypergraphs H with minimum vertex degree at least c(|V (H)| ^{-1}/2); for some c; leaving a gap for k ≥ 5; which vanishes as k → 1. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.

- Record ID
- UAM6a208a9beb87411884343780d1293ac8
- Author
- Journal series
- Discrete Mathematics and Theoretical Computer Science, ISSN 1462-7264, [1365-8050]
- Issue year
- 2013
- Vol
- 15
- Pages
- 121-138
- ASJC Classification
- ; ;
- Language
- (en) English
- Score (nominal)
- 20
- Score source
- journalList
- Score
- Publication indicators
- = 0; : 2013 = 0.687; : 2013 (2 years) = 0.609 - 2013 (5 years) =0.676

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM6a208a9beb87411884343780d1293ac8/

- URN
`urn:amu-prod:UAM6a208a9beb87411884343780d1293ac8`

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.