The connection between the chromatic numbers of a hypergraph and its 1-intersection graph

A well known problem from an excellent book of Lovász states that any hypergraph with the property that no pair of hyperedges intersect in exactly one vertex can be properly 2-colored. Motivated by this as well as recent works of Keszegh and of Gyárfás et al. we study the 1-intersection graph of a hypergraph. The 1-intersection graph encodes those pairs of hyperedges in a hypergraph that intersect in exactly one vertex. We prove for k ϵ {2, 4} that all hypergraphs whose 1-intersection graph is k-partite can be properly k-colored.. Authors: Blázsik, Zoltán L. [Univ. of Szeged (Hungary). HUN-REN Alfréd Rényi Institute of Mathematics] (ORCID:0000000318779983); Lemons, Nathan Wishard [Los Alamos National Laboratory (LANL), Los Alamos, NM (United States)] (ORCID:0000000258046672). DOE Contract: 89233218CNA000001. Subjects: 1-intersection graph of hypergraphs; 97 MATHEMATICS AND COMPUTING; Bipartite graph; Chromatic number; Greedy coloring; Recoloring process