Minimal Non-C-Perfect Hypergraphs with Circular Symmetry

Abstract

In this research paper, we study 3-uniform hypergraphs H=(X,E) with circular symmetry. Two parameters are considered: the largest size α(H) of a set S⊂X not containing any edge E∈E, and the maximum number χ¯(H) of colors in a vertex coloring of H such that each E∈E contains two vertices of the same color. The problem considered here is to characterize those H in which the equality χ¯(H′)=α(H′) holds for every induced subhypergraph H′=(X′,E′) of H. A well-known objection against χ¯(H′)=α(H′) is where ∩E∈E′E=1, termed “monostar”. Steps toward a solution to this approach is to investigate the properties of monostar-free structures. All such H are completely identified up to 16 vertices, with the aid of a computer. Most of them can be shown to satisfy χ¯(H)=α(H), and the few exceptions contain one or both of two specific induced subhypergraphs H5⥁, H6⥁ on five and six vertices, respectively, both with χ¯=2 and α=3. Furthermore, a general conjecture is raised for hypergraphs of prime orders.

Keywords

• hypergraph
• coloring
• circular symmetry
• independent set
• upper chromatic number
• C-perfect hypergraph