Attempting perfect hypergraphs

Maria Chudnovsky, Gil Kalai

Research output: Contribution to journalArticlepeer-review


We study several extensions of the notion of perfect graphs to k-uniform hypergraphs. One main definition extends to hypergraphs the notion of perfect graphs based on coloring. Let G be a k-uniform hypergraph. A coloring of a k-uniform hypergraph G is proper if it is a coloring of the (k − 1)-tuples with elements in V(G) in such a way that no edge of G is a monochromatic Kkk−1 . A k-uniform hypergraph G is Cω-perfect if for every induced subhypergraph G′ of G we have: if X ⊆ V(G′) with ∣X∣ < k − 1, then there is a proper (ω(G′) − k + 2)-coloring of G′ (so (k − 1)-tuples are colored) that restricts to a proper (ω(G′) − k + 2)-coloring of lk G′(X) (so (k − ∣X∣ − 1)-tuples are colored). Another main definition is the following: A k-uniform hypergraph G is hereditary perfect (or, briefly, H-perfect) if all links of sets of (k − 2) vertices are perfect graphs. The notion of Cω perfectness is not closed under complementation (for k > 2) and we define G to be doubly perfect if both G and its complement are Cω perfect. We study doubly-perfect hypergraphs: In addition to perfect graphs nontrivial doubly-perfect graphs consist of a restricted interesting class of 3-uniform hypergraphs, and within this class we give a complete characterization of doubly-perfect H-perfect hypergraphs.

Original languageEnglish (US)
Pages (from-to)133-151
Number of pages19
JournalIsrael Journal of Mathematics
Issue number1
StatePublished - Sep 2023

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Attempting perfect hypergraphs'. Together they form a unique fingerprint.

Cite this