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

Abstract : In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c\binom|V(H)|-1r-1, or minimum degree of a pair of vertices at least c\binom|V(H)|-2r-2, has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain first optimal dichotomy results for 2-colorings of r-uniform hypergraphs. For each problem, for every r≥q 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^\lfloor 4/ε\rfloor+2\log n) with some ε>0. This algorithm becomes more efficient in the case of 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 k-coloring of 3-uniform hypergraphs H with minimum vertex degree at least c\binom|V(H)|-12, for some c, leaving a gap for k≥q 5 which vanishes as k→ ∞.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.121--137
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980762
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:40
Dernière modification le : jeudi 7 septembre 2017 - 01:03:46
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:51:33

Fichier

2014-8173-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00980762, version 1

Collections

Citation

Edyta Szymańska. The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degree. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.121--137. 〈hal-00980762〉

Partager

Métriques

Consultations de la notice

679

Téléchargements de fichiers

909