2024/06/17 by Zoltán L. Blázsik, Blázsik, Zoltán L., Nathan W. Lemons +1
Computer Science · #05C15 #Combinatorics (math.CO) #Data Visualization and Analytics #FOS: Mathematics #Image Retrieval and Classification Techniques #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2406.12118
openalex publication_date 2024/06/17 · openalex created_date 2024/06/20 · openalex updated_date 2026/08/01
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.