Two-coloring triples such that in each color class every element is missed at least once

Keszegh, Balázs (2020) Two-coloring triples such that in each color class every element is missed at least once. GRAPHS AND COMBINATORICS. ISSN 0911-0119

Preview

Text s00373-020-02217-1.pdf Download (341kB) | Preview

Abstract

We give a characterization of finite sets of triples of elements (e.g., positive integers) that can be colored with two colors such that for every element i in each color class there exists a triple which does not contain i. We give a linear (in the number of triples) time algorithm to decide if such a coloring exists and find one if it does. We also consider generalizations of this result and an application to a matching problem, which motivated this study. Finally, we show how these results translate to results about colorings of hypergraphs in which the degree of every vertex is k less than the number of hyperedges.

Actions (login required)

Edit Item