TY - JOUR

T1 - Attempting perfect hypergraphs

AU - Chudnovsky, Maria

AU - Kalai, Gil

N1 - Publisher Copyright:
© 2023, The Hebrew University of Jerusalem.

PY - 2023/9

Y1 - 2023/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85173706238&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85173706238&partnerID=8YFLogxK

U2 - 10.1007/s11856-023-2506-8

DO - 10.1007/s11856-023-2506-8

M3 - Article

AN - SCOPUS:85173706238

SN - 0021-2172

VL - 256

SP - 133

EP - 151

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

IS - 1

ER -