On conjectures of Berge and Chvátal
type: Item
instance of: scholarly article
title: On conjectures of Berge and Chvátal
zbMATH Open document ID: 0789.05073
DOI: 10.1016/0012-365X(94)90086-8
author: Mario Gionfriddo
author: Zsolt Tuza
published in: Discrete Mathematics
publication date: 1994-05-24T00:00:00Z
review text: A hypergraph \(H\) is linear if any two of its edges share at most one vertex. The hereditary closure \(H^ \wedge\) of \(H\) is the collection of all nonempty subsets of the edges of \(H\). \(\Delta(H)\) is the maximum number of edges of \(H\) incident to a given vertex; \(\Delta_ 0(H)\) is the maximum number of pairwise intersecting edges in \(H\); \(q(H)\) is the chromatic index of \(H\). Conjecture 1 (C. Berge, 1990): If \(H\) is linear, then \(\Delta (H^ \wedge)=q(H^ \wedge)\). Conjecture 2 (V. Chvátal, 1974): If \(H=H^ \wedge\), then \(\Delta (H)=\Delta_ 0(H)\). The authors prove Conjecture 1 for all resolvable Steiner systems \(H\) of type \(S(2,k,n)\) and Conjecture 2 for every sufficiently large BIBD if the block size and the number of blocks containing a given pair of points are fixed.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 05B07
zbMATH DE Number: 500609
zbMATH Keywords: conjectures of Berge and Chvátal
zbMATH Keywords: hypergraph
zbMATH Keywords: chromatic index
zbMATH Keywords: Steiner systems
zbMATH Keywords: BIBD
reviewed by: G. Gutin
Wikidata QID: Q123295659
MaRDI profile type: Publication
cites work: Q4063504
cites work: Nombres de coloration de l'hypergraphe h-parti complet
cites work: Q4087226
cites work: Q3983098
cites work: Q4141851
cites work: Q4060998
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: Q4745849
cites work: The Existence and Construction of Balanced Incomplete Block Designs
cites work: SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: On the number of latent subsets of intersecting collections
cites work: Great intersecting families of edges in hereditary hypergraphs
cites work: Q4182515
cites work: Chvatal's conjecture and point-intersections
cites work: Q3901518
cites work: Q4060997
cites work: Critical hypergraphs and interesting set-pair systems
cites work: Some results about the Chvatal conjecture
description: scientific article; zbMATH DE number 500609