About Berge–Füredi’s conjecture on the chromatic index of hypergraphs

Alain Bretto; Alain Faisant; François Hennecart

doi:10.5802/crmath.739

Research article - Combinatorics

About Berge–Füredi’s conjecture on the chromatic index of hypergraphs

Alain Bretto ¹; Alain Faisant ²; François Hennecart ²

¹ Université Caen Normandie, GREYC CNRS-UMR 6072, Caen, France
² Université Jean Monnet, ICJ UMR5208, CNRS, École Centrale de Lyon, INSA Lyon, Université Claude Bernard Lyon 1, 42023 Saint-Étienne, France

Comptes Rendus. Mathématique, Volume 363 (2025), pp. 323-328.

Abstract (Original language)
Résumé

We prove that the chromatic index of a hypergraph $\mathcal{H}$ satisfies the Berge–Füredi conjectured bound $\mathrm{q}(\mathcal{H}\le \Delta \bigl ([\mathcal{H}_2]\bigr )+1$ under certain hypotheses on the antirank $\mathrm{ar}(\mathcal{H})$ or on the maximum degree $\Delta (\mathcal{H})$. This provides sharp information in connection with the Erdős–Faber–Lovász conjecture which deals with the coloring of a family of cliques that intersect pairwise in at most one vertex.

Nous montrons que l’indice chromatique d’un hypergraphe satisfait la borne conjecturée indépendamment par Berge et Füredi, $\mathrm{q}(\mathcal{H}\le \Delta \bigl ([\mathcal{H}_2]\bigr )+1$ sous certaines conditions portant sur son antirang $\mathrm{ar}(\mathcal{H})$ ou son degré maximum $\Delta (\mathcal{H})$. Ces résultats fournissent des informations sur la conjecture de Erdős, Faber and Lovász qui traite de la coloration d’une famille de cliques se coupant deux à deux en au plus un sommet.

Received: 2024-03-12
Revised: 2025-03-10
Accepted: 2025-03-11
Published online: 2025-04-08

DOI: 10.5802/crmath.739

Classification: 05C15
Keywords: Hypergraphs, hyperedge coloring, chromatic index
Mots-clés : Hypergraphes, coloration des hyperarêtes, indice chromatique

Author's affiliations:

Alain Bretto ¹; Alain Faisant ²; François Hennecart ²

¹ Université Caen Normandie, GREYC CNRS-UMR 6072, Caen, France
² Université Jean Monnet, ICJ UMR5208, CNRS, École Centrale de Lyon, INSA Lyon, Université Claude Bernard Lyon 1, 42023 Saint-Étienne, France

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{CRMATH_2025__363_G3_323_0,
     author = {Alain Bretto and Alain Faisant and Fran\c{c}ois Hennecart},
     title = {About {Berge{\textendash}F\"uredi{\textquoteright}s} conjecture on the chromatic index of hypergraphs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {323--328},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {363},
     year = {2025},
     doi = {10.5802/crmath.739},
     language = {en},
}

TY  - JOUR
AU  - Alain Bretto
AU  - Alain Faisant
AU  - François Hennecart
TI  - About Berge–Füredi’s conjecture on the chromatic index of hypergraphs
JO  - Comptes Rendus. Mathématique
PY  - 2025
SP  - 323
EP  - 328
VL  - 363
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.739
LA  - en
ID  - CRMATH_2025__363_G3_323_0
ER  -

%0 Journal Article
%A Alain Bretto
%A Alain Faisant
%A François Hennecart
%T About Berge–Füredi’s conjecture on the chromatic index of hypergraphs
%J Comptes Rendus. Mathématique
%D 2025
%P 323-328
%V 363
%I Académie des sciences, Paris
%R 10.5802/crmath.739
%G en
%F CRMATH_2025__363_G3_323_0

Alain Bretto; Alain Faisant; François Hennecart. About Berge–Füredi’s conjecture on the chromatic index of hypergraphs. Comptes Rendus. Mathématique, Volume 363 (2025), pp. 323-328. doi : 10.5802/crmath.739. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.739/

References
Cited by

[1] Claude Berge On the chromatic index of a linear hypergraph and the Chvátal Conjecture, Ann. N.Y. Acad. Sci., Volume 555 (1989), pp. 40-44 | DOI | Zbl

[2] Claude Berge Motivations and history of some of my conjectures, Discrete Math., Volume 165-166 (1997), pp. 61-70 | DOI | MR | Zbl

[3] Alain Bretto; Alain Faisant; François Hennecart Elements of Graph Theory: From Basic Concepts to Modern Developments, EMS Textbooks in Mathematics, European Mathematical Society, 2022, xv+486 pages | DOI | MR | Zbl

[4] Alain Bretto; Alain Faisant; François Hennecart The Berge–Füredi Conjecture on the chromatic index of hypergraphs with large hyperedges (2024) | arXiv

[5] Tomáš Dvořák Chromatic index of hypergraphs and Shannon’s Theorem, Eur. J. Comb., Volume 21 (2000), pp. 585-591 | DOI | MR | Zbl

[6] Zoltan Füredi The chromatic index of simple hypergraphs, Graphs Comb., Volume 2 (1986) no. 1, pp. 89-92 | DOI | MR | Zbl

[7] Zhimin Wang The Erdős–Faber–Lovász Conjecture for gap-restricted hypergraphs, Engineering, Volume 16 (2024), pp. 47-59 | DOI

[8] Guo-Hui Zhang; Brett Skinner Chromatic index of simple hypergraphs, Discrete Math., Volume 343 (2020) no. 12, 112087, 7 pages | DOI | MR | Zbl

Cited by Sources:

Comments - Policy