# About Berge-Füredi's conjecture on the chromatic index of hypergraphs

Alain Bretto, Alain Faisant, François Hennecart

► To cite this version:

Alain Bretto, Alain Faisant, François Hennecart. About Berge-Füredi's conjecture on the chromatic index of hypergraphs. Comptes rendus de l'Académie des sciences. Série I, Mathématique, 2025, 363, pp.323-328. 10.5802/crmath.739. hal-04740842

HAL Id: hal-04740842

https://hal.science/hal-04740842v1

Submitted on 19 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Comptes Rendus
Mathématique

Alain Bretto, Alain Faisant and François Hennecart

About Berge-Füredi's conjecture on the chromatic index of hypergraphs

Volume 363 (2025), p. 323-328

Online since: 8 April 2025

https://doi.org/10.5802/crmath.739

<figure><img src="image_2.png" /></figure>

This article is licensed under the
CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.
http://creativecommons.org/licenses/by/4.0/
Research article / *Article de recherche*
Combinatorics / *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*

Alain Bretto<sup>a</sup>, Alain Faisant<sup>b</sup> and François Hennecart<sup>*, b</sup>

<sup>a</sup> Université Caen Normandie, GREYC CNRS-UMR 6072, Caen, France

<sup>b</sup> Université Jean Monnet, ICJ UMR5208, CNRS, École Centrale de Lyon, INSA Lyon, Université Claude Bernard Lyon 1, 42023 Saint-Étienne, France

*E-mails:* alain.bretto@info.unicaen.fr, faisant@univ-st-etienne.fr, francois.hennecart@univ-st-etienne.fr

**Abstract.** We prove that the chromatic index of a hypergraph $\mathcal{H}$ satisfies the Berge–Füredi conjectured bound $q(\mathcal{H} \le \Delta([\mathcal{H}_2]) + 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.

**Résumé.** Nous montrons que l'indice chromatique d'un hypergraphe satisfait la borne conjecturée indépendamment par Berge et Füredi, $q(\mathcal{H} \le \Delta([\mathcal{H}_2]) + 1$ sous certaines conditions portant sur son antirank $\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.

**Keywords.** Hypergraphs, hyperedge coloring, chromatic index.

**Mots-clés.** Hypergraphes, coloration des hyperarêtes, indice chromatique.

**2020 Mathematics Subject Classification.** 05C15.

Manuscript received 12 March 2024, revised 10 March 2025, accepted 11 March 2025.

## 1. Introduction

Berge–Füredi's conjecture (cf. [1,2,6] and Meyniel, unpublished communication) extends to linear hypergraphs Vizing's theorem on the chromatic index of graphs (see [3, Theorem 7.2.2]). It asserts that the chromatic index of any linear hypergraph $\mathcal{H} = (V, E)$ without loop satisfies

$$q(\mathcal{H}) \le \Delta([\mathcal{H}]_2) + 1. \qquad (1)$$

This bound was first conjectured around 1986. Since then, to our knowledge, only few advances have been made. It has been recently proved [8] that (1) holds whenever $\Delta([\mathcal{H}]_2) \le 5$. In the present paper we obtain new conditional results where the antirank $\mathrm{ar}(\mathcal{H})$ and the maximum degree $\Delta(\mathcal{H})$ are involved together with the maximum degree $\Delta([\mathcal{H}]_2)$ of the 2-section of $\mathcal{H}$.

If $\mathcal{H}$ is linear then $\Delta([\mathcal{H}]_2) \le |V|-1$. Hence bound (1) implies Erdős–Faber–Lovász conjecture asserting that $q(\mathcal{H}) \le |V|$ for any linear hypergraph $\mathcal{H}$.

<footnote>*Corresponding author</footnote>
## 2. Notation and statements

Let $\mathcal{H} = (V, E)$ be a hypergraph. For $x \in V$ and $e \in E$, we let

$$ \deg_{\mathcal{H}}(x) = |\{a \in E : x \in a\}|, \quad d_{\mathcal{H}}(e) = |\{a \in E \setminus \{e\} : a \cap e \neq \emptyset\}|, $$

be the degree of vertex $x$ and the degree of hyperedge $e$ in $\mathcal{H}$, respectively. Then, we define respectively the rank, the antirank, the maximum degree and the minimum degree of $\mathcal{H}$ by

$$ \mathrm{r}(\mathcal{H}) = \max_{e \in E} |e|, \quad \mathrm{ar}(\mathcal{H}) = \min_{e \in E} |e|, \quad \Delta(\mathcal{H}) = \max_{x \in V} \deg_{\mathcal{H}}(x), \quad \delta(\mathcal{H}) = \min_{x \in V} \deg_{\mathcal{H}}(x). $$

A loop in a hypergraph $\mathcal{H}$ is a hyperedge $e$ such that $|e| = 1$.

The 2-section of $\mathcal{H} = (V, E)$ is the loopless multigraph $[\mathcal{H}]_2 = (V, A)$ with $k$ many edges between $x, y \in V$, $x \neq y$, if there are $k$ hyperedges in $\mathcal{H}$ containing both $x$ and $y$. We have

$$ \Delta([\mathcal{H}]_2) \geq (\mathrm{ar}(\mathcal{H}) - 1)\Delta(\mathcal{H}). \qquad (2) $$

The chromatic index of $\mathcal{H}$, denoted by $q(\mathcal{H})$, is the least integer $q$ such that there exists a map $c: E \to \{1, 2, \dots, q\}$ satisfying

$$ \forall e, e' \in E, (c(e) = c(e') \implies e \cap e' = \emptyset \text{ or } e = e'). $$

The map $c$ is called a hyperedge-coloring of $\mathcal{H}$ and the image of $E$ through $c$ forms the set of colors.

A hypergraph $\mathcal{H} = (V, E)$ is said linear if for any pair of distinct hyperedges $e, e' \in E$, we have $|e \cap e'| \le 1$. In this case $[\mathcal{H}]_2$ reduces to a simple graph.

Recently it has been established that if $\mathcal{H}$ is a linear hypergraph satisfying

$$ \mathrm{ar}(\mathcal{H}) \geq \sqrt{|V|}, \qquad (3) $$

then $q(\mathcal{H}) \le |V|$ (cf. [7]). This upper bound has been improved in [4] where it is shown that under the same hypotheses on $\mathcal{H}$, then (1) actually holds. In this note we show that condition (3) can be weakened by proving the following sharper result.

**Theorem 1.** Let $\mathcal{H} = (V, E)$ be a loopless hypergraph such that $\mathrm{ar}(\mathcal{H}) \ge \sqrt{\Delta([\mathcal{H}]_2) + 1}$. Then $q(\mathcal{H}) \le \Delta([\mathcal{H}]_2) + 1$.

Note that we do not assume in the above statement that $\mathcal{H}$ is linear. We will propose an approach supported by the notion of critical hypergraph (see also Section 6.1 for additional comments).

We will prove the following key result which has its own interest. $\mathcal{H}$ is said $k$-uniform (resp. $d$-regular) if $\forall e \in E, |e| = k$ (resp. $\forall x \in V, \deg_{\mathcal{H}}(x) = d$).

**Theorem 2.** Let $k \ge 2$ and $\mathcal{H} = (V, E)$ be a $k$-uniform and $(k+1)$-regular linear hypergraph. Then $q(\mathcal{H}) \le \Delta([\mathcal{H}]_2) + 1$.

The following corollary will be derived from Theorem 1.

**Corollary 3.** Let $\mathcal{H} = (V, E)$ be a loopless hypergraph such that

$$ \Delta(\mathcal{H}) \le \sqrt{\Delta([\mathcal{H}]_2) + 1 + 1}. \qquad (4) $$

Then $q(\mathcal{H}) \le \Delta([\mathcal{H}]_2) + 1$.
### 3. Proof of Theorem 1

In [4] we exploited the notion of critical hyperedge. A hyperedge $e$ is said critical if $q(\mathcal{H} \setminus e) = q(\mathcal{H}) - 1$. Hypergraph $\mathcal{H}$ is a critical hypergraph if all its hyperedges are critical. Since the addition of $e$ to $\mathcal{H} \setminus e$ needs a new color, $e$ must intersect every color of $\mathcal{H} \setminus e$. So we have the following.

**Lemma 4 ([4, Lemma 3.2]).** Let $\mathcal{H} = (V, E)$ be a hypergraph without loop and $e \in E$ be a critical hyperedge. Then $q(\mathcal{H}) - 1 \le d_{\mathcal{H}}(e)$.

We may assume that $\mathcal{H}$ is connected and critical since $\mathrm{ar}(\mathcal{H}') \ge \mathrm{ar}(\mathcal{H})$ and $\Delta([\mathcal{H}']_2) \le \Delta([\mathcal{H}]_2)$ for any partial hypergraph $\mathcal{H}'$ of $\mathcal{H}$. Let $e \in E$ be of minimum cardinality $k := \mathrm{ar}(\mathcal{H})$. We have

$$d_{\mathcal{H}}(e) = \sum_{\substack{a \in E \\ a \cap e \neq \emptyset}} 1 \le \sum_{a \in E \setminus \{e\}} |a \cap e| = \sum_{x \in V} \sum_{\substack{a \in E \\ a \notin x}} 1 = \sum_{x \in e} (\mathrm{deg}_{\mathcal{H}}(x) - 1), \quad (5)$$

and equality occurs when $\mathcal{H}$ is linear. Then by Lemma 4 we get

$$q(\mathcal{H}) - 1 = q(\mathcal{H} \setminus e) \le d_{\mathcal{H}}(e) \le k(\Delta(\mathcal{H}) - 1) = (k-1)\Delta(\mathcal{H}) - (k - \Delta(\mathcal{H})),$$

so

$$q(\mathcal{H}) \le \Delta([\mathcal{H}]_2) + 1 - (k - \Delta(\mathcal{H})). \quad (6)$$

Our hypothesis implies $\Delta([\mathcal{H}]_2) \le k^2 - 1$. We distinguish two cases.

* If $\Delta([\mathcal{H}]_2) < k^2 - 1$ we get by (2) that $\Delta(\mathcal{H}) < k + 1$ thus $\Delta(\mathcal{H}) \le k$, yielding the required upper bound for $q(\mathcal{H})$ by (6).

* Assume that $\Delta([\mathcal{H}]_2) = k^2 - 1$. We thus have to prove that $q(\mathcal{H}) \le k^2$. If there exists $e \in E$ such that $|e| = k$ and $d_{\mathcal{H}}(e) \le k^2 - 1$ then $q(\mathcal{H}) \le d_{\mathcal{H}}(e) + 1 \le k^2$ by Lemma 4 and we are done. Otherwise

$$d_{\mathcal{H}}(e) \ge k^2 \quad \text{for any hyperedge } e \text{ of cardinality } k. \quad (7)$$

We shall see that $\mathcal{H}$ is a very special hypergraph.

- Let $e \in E$ be of cardinality $k$. By (2) we have $\Delta(\mathcal{H}) \le k + 1$, thus by (7) and (5) we get

$$k^2 \le d_{\mathcal{H}}(e) \le \sum_{x \in e} (\mathrm{deg}_{\mathcal{H}}(x) - 1) \le k(\Delta(\mathcal{H}) - 1) \le k(k + 1 - 1) = k^2.$$

We infer

$$d_{\mathcal{H}}(e) = k^2 \quad \text{and} \quad \mathrm{deg}_{\mathcal{H}}(x) - 1 = k \quad \text{for any } x \in e. \quad (8)$$

- Let $a \in E$ such that $a \cap e \neq \emptyset$. Let $x \in a \cap e$. We have

$$\begin{align*}
k^2 - 1 &= \Delta([\mathcal{H}]_2) \ge \mathrm{deg}_{[\mathcal{H}]_2}(x) = \sum_{\substack{b \in E \\ b \in x}} (|b| - 1) \\
&= |a| - 1 + \sum_{\substack{b \in E \setminus \{a\} \\ b \in x}} (|b| - 1) \\
&\ge |a| - 1 + (\mathrm{deg}_{\mathcal{H}}(x) - 1)(k - 1) \\
&= |a| - 1 + k(k - 1) \\
&\ge k^2 - 1,
\end{align*}$$

giving $|a| = k$.

- Since $\mathcal{H}$ is connected we infer that $|a| = k$ for any $a \in E$. Hence $\mathcal{H}$ is $k$-uniform and $(k + 1)$-regular. By (5) and (8), we have $|a \cap e| = 1$ whenever $a \cap e \neq \emptyset$. Thus $\mathcal{H}$ is linear. The proof will be completed when Theorem 2 will be established.
## 4. Proof of Theorem 2

By assumption we have

$$k|e| = (k+1)|V|, \quad \Delta([\mathcal{H}]_2) = k^2 - 1 \quad \text{and} \quad \forall e \in E, d_{\mathcal{H}}(e) = k^2. \qquad (9)$$

Since $\mathcal{H}$ is linear, its line-graph $L(\mathcal{H})$ is the simple graph whose vertices are hyperedges of $\mathcal{H}$ and such that there is an edge between $e, e' \in E, e \neq e'$, if $e \cap e' \neq \emptyset$. We have $\deg_{L(\mathcal{H})}(e) = d_{\mathcal{H}}(e)$ for any $e \in E$.

By (9), each vertex $e$ of $L(\mathcal{H})$ has degree $\deg_{L(\mathcal{H})}(e) = k^2$. Hence $L(\mathcal{H})$ is $k^2$-regular. Since $q(\mathcal{H})$ coincides with $\chi(L(\mathcal{H}))$, namely the chromatic number of the simple graph $L(\mathcal{H})$, we infer from Brooks' theorem (see [3, Theorem 7.1.9, p. 238]) that either

$$q(\mathcal{H}) \le \Delta(L(\mathcal{H})) = k^2 = \Delta([\mathcal{H}]_2) + 1$$

or $L(\mathcal{H})$ is complete or an odd-length cycle. If $L(\mathcal{H})$ were a complete graph, we would have $|e| = k^2 + 1$ implying by (9) that $(k+1)$ divides $k(k^2+1)$, which gives a contradiction since $k \ge 2$. If $L(\mathcal{H})$ were a cycle, we would have $d_{\mathcal{H}}(e) = \deg_{L(\mathcal{H})}(e) = 2$ for any $e \in E$, a contradiction. This ends the proof of Theorem 2.

## 5. Proof of Corollary 3

Let $\mathcal{H}' = (V, E')$ be a critical partial hypergraph of $\mathcal{H}$ such that $q(\mathcal{H}') = q(\mathcal{H})$.

* If $\ar(\mathcal{H}') \ge \sqrt{\Delta([\mathcal{H}']_2) + 1}$ we infer from Theorem 1 that

$$q(\mathcal{H}) = q(\mathcal{H}') \le \Delta([\mathcal{H}']_2) + 1 \le \Delta([\mathcal{H}]_2) + 1.$$

* If $\ar(\mathcal{H}') < \sqrt{\Delta([\mathcal{H}']_2) + 1}$ then we take $e \in E'$ such that $|e| = \ar(\mathcal{H}')$. By Lemma 4 and using (5) with $\mathcal{H}'$ in place of $\mathcal{H}$, we get

$$\begin{align*}
q(\mathcal{H}) - 1 &= q(\mathcal{H}') - 1 \le d_{\mathcal{H}'}(e) \\
&\le \sum_{x \in e} (\deg_{\mathcal{H}'}(x) - 1) \\
&\le |e|(\Delta(\mathcal{H}') - 1) \\
&= \ar(\mathcal{H}') (\Delta(\mathcal{H}') - 1) \\
&< \sqrt{\Delta([\mathcal{H}']_2) + 1} (\Delta(\mathcal{H}') - 1) \\
&\le \sqrt{\Delta([\mathcal{H}]_2) + 1} (\Delta(\mathcal{H}) - 1) \\
&\le \Delta([\mathcal{H}]_2) + 1
\end{align*}$$

by (4). Hence $q(\mathcal{H}) \le \Delta([\mathcal{H}]_2) + 1$ as wanted.

## 6. Remarks and questions

### 6.1.

We should notice that when $\ar(\mathcal{H}) > \sqrt{\Delta([\mathcal{H}]_2) + 1}$ then the desired bound $q(\mathcal{H}) \le \Delta([\mathcal{H}]_2) + 1$ can be equally deduced from the greedy algorithm for coloring hyperedges (see for instance [5, p. 586]) which yields

$$q(\mathcal{H}) \le \max_{\mathcal{r}(\mathcal{H}) \ge k \ge \ar(\mathcal{H})} k \left\lfloor \frac{\Delta([\mathcal{H}]_2)}{k-1} - 1 \right\rfloor + 1.$$

Here we use a different approach which allows us to solve in addition the equality case $\ar(\mathcal{H}) = \sqrt{\Delta([\mathcal{H}]_2) + 1}$.
## 6.2.

When the maximum degree $\Delta(\mathcal{H})$ satisfies $\Delta(\mathcal{H}) > \sqrt{\Delta([\mathcal{H}]_2) + 1} + 1$, Corollary 3 is no longer usable. However at the cost of an additional condition on the rank $r(\mathcal{H}) = \max_{e \in E} |e|$, we can notice that (1) remains valid for linear hypergraphs $\mathcal{H}$. Let $\delta_2 := \sqrt{\Delta([\mathcal{H}]_2)}$ and assume that

$$r(\mathcal{H}) = \delta_2 - u, \quad u > 0,$$

$$\Delta(\mathcal{H}) = \delta_2 + 1 + v, \quad v > 0.$$

Then

$$q(\mathcal{H}) = \chi(L(\mathcal{H})) \le \Delta(L(\mathcal{H})) + 1 \le r(\mathcal{H})(\Delta(\mathcal{H}) - 1) + 1 = (\delta_2 - u)(\delta_2 + v) + 1.$$

Thus (1) holds whenever $(v-u)\delta_2 \le uv$, that is $\frac{1}{u} \le \frac{1}{v} + \frac{1}{\delta_2}$.

## 6.3.

If $\mathcal{H}$ is supposed linear, in the extremal case $\Delta([\mathcal{H}]_2) = |V| - 1$, $\ar(\mathcal{H}) = |V|^{1/2}$ in Theorem 1 the authors obtained in [4] a much better upper bound for $q(\mathcal{H})$, namely $q(\mathcal{H}) \le \frac{1}{2}(\Delta([\mathcal{H}]_2) + 1 + \sqrt{\Delta([\mathcal{H}]_2) + 1}) + 1$. How can the upper bound for $q(\mathcal{H})$ be improved under the sole condition $\ar(\mathcal{H}) = \sqrt{\Delta([\mathcal{H}]_2) + 1}$?

## 6.4.

Theorem 2 deals with $k$-uniform and $d$-regular linear hypergraphs when $d = k + 1$ and provides the required bound (1). For general $k, d$ satisfying $k \le d - 2$, the line-graph $L(\mathcal{H})$ is $k(d-1)$-regular and Brooks' theorem provides the (non sufficiently sharp) inequality $q(\mathcal{H}) = \chi(L(\mathcal{H})) \le \Delta(L(\mathcal{H})) = k(d-1)$ while $\Delta([\mathcal{H}]_2) = d(k-1)$.

## 6.5.

More generally let $\mathcal{H}$ be a $k$-uniform linear hypergraph with $k \ge 2$ and set $\delta_2 := \sqrt{\Delta([\mathcal{H}]_2)}$. Then (1) holds if at least one of the following conditions is satisfied:

(1) $k = 2$: Vizing's theorem (see [3, Theorem 7.2.2, p. 249]);

(2) $k \ge \sqrt{\Delta([\mathcal{H}]_2) + 1}$: Theorem 1;

(3) $\Delta([\mathcal{H}]_2) = k^2$ which implies $\Delta(\mathcal{H}) \le \sqrt{\Delta([\mathcal{H}]_2) + 1}$: Corollary 3;

(4) $3 \le k < \delta_2$ and $\frac{1}{\delta_2 - k} \le \frac{1}{\Delta(\mathcal{H}) - \delta_2 - 1} + \frac{1}{\delta_2}$: see Section 6.2.

In order to solve Berge-Füredi's conjecture for all linear uniform hypergraphs, it thus remains to consider the case where

$$3 \le k < \delta_2 < \Delta(\mathcal{H}) - 1 \quad \text{and} \quad \frac{1}{\delta_2 - k} > \frac{1}{\Delta(\mathcal{H}) - \delta_2 - 1} + \frac{1}{\delta_2}.$$

We may likewise ask the following question: is Berge-Füredi's conjecture in all its generality implied by its validity for linear uniform hypergraphs?

## Declaration of interests

The authors do not work for, advise, own shares in, or receive funds from any organization that could benefit from this article, and have declared no affiliations other than their research organizations.
References

[1] C. Berge, "On the chromatic index of a linear hypergraph and the Chvátal Conjecture", *Ann. N.Y. Acad. Sci.* **555** (1989), pp. 40–44.

[2] C. Berge, "Motivations and history of some of my conjectures", *Discrete Math.* **165-166** (1997), pp. 61–70.

[3] A. Bretto, A. Faisant and F. Hennecart, *Elements of Graph Theory: From Basic Concepts to Modern Developments*, EMS Textbooks in Mathematics, European Mathematical Society, 2022, pp. xv+486.

[4] A. Bretto, A. Faisant and F. Hennecart, "The Berge–Füredi Conjecture on the chromatic index of hypergraphs with large hyperedges", 2024. Online at https://arxiv.org/abs/2403.06850.

[5] T. Dvořák, "Chromatic index of hypergraphs and Shannon's Theorem", *Eur. J. Comb.* **21** (2000), pp. 585–591.

[6] Z. Füredi, "The chromatic index of simple hypergraphs", *Graphs Comb.* **2** (1986), no. 1, pp. 89–92.

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

[8] G.-H. Zhang and B. Skinner, "Chromatic index of simple hypergraphs", *Discrete Math.* **343** (2020), no. 12, article no. 112087 (7 pages).