Discrete Mathematics & Theoretical Computer Science |

- 1 Faculty of Mathematics and Computer Science [Poznan]

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→ ∞.

Source: HAL:hal-00980762v1

Volume: Vol. 15 no. 2

Section: Discrete Algorithms

Published on: July 12, 2013

Accepted on: June 9, 2015

Submitted on: August 2, 2011

Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 424 times.

This article's PDF has been downloaded 2527 times.