Coloring 2-Intersecting Hypergraphs

  • Lucas Colucci
  • András Gyárfás
Keywords: Hypergraph coloring

Abstract

A hypergraph is 2-intersecting if any two edges intersect in at least two vertices. Blais, Weinstein and Yoshida asked (as a first step to a more general problem) whether every 2-intersecting hypergraph has a vertex coloring with a constant number of colors so that each hyperedge has at least $\min(|e|,3)$ colors. We show that there is such a coloring with at most 5 colors (which is best possible).
Published
2013-09-13
Article Number
P37