Comptes Rendus
Article de recherche - Combinatoire
About Berge–Füredi’s conjecture on the chromatic index of hypergraphs
[Sur la conjecture de Berge–Füredi sur l’indice chromatique des hypergraphes]
Comptes Rendus. Mathématique, Volume 363 (2025), pp. 323-328.

Nous montrons que l’indice chromatique d’un hypergraphe satisfait la borne conjecturée indépendamment par Berge et Füredi, q(HΔ([H2])+1 sous certaines conditions portant sur son antirang ar(H) ou son degré maximum Δ(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.

We prove that the chromatic index of a hypergraph H satisfies the Berge–Füredi conjectured bound q(HΔ([H2])+1 under certain hypotheses on the antirank ar(H) or on the maximum degree Δ(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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/crmath.739
Classification : 05C15
Keywords: Hypergraphs, hyperedge coloring, chromatic index
Mots-clés : Hypergraphes, coloration des hyperarêtes, indice chromatique

Alain Bretto 1 ; Alain Faisant 2 ; François Hennecart 2

1 Université Caen Normandie, GREYC CNRS-UMR 6072, Caen, France
2 Université Jean Monnet, ICJ UMR5208, CNRS, École Centrale de Lyon, INSA Lyon, Université Claude Bernard Lyon 1, 42023 Saint-Étienne, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@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/

[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

Cité par Sources :

Commentaires - Politique