<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%~MoulinÃ© par MaN_auto v.0.33.5 2025-03-24 14:02:30
\documentclass[CRMATH,Unicode,XML,biblatex]{cedram}

\TopicFR{Combinatoire}
\TopicEN{Combinatorics}

\addbibresource{CRMATH_Hennecart_20240192.bib}

\usepackage{amssymb}
\usepackage{mathtools}

\newcommand{\h}{\mathcal{H}}
\newcommand{\degh}{\deg_{\h}}

\newcommand{\Dunh}{\Delta(\h)}
\newcommand{\Ddeuxh}{\Delta\bigl([\h]_2\bigr)}

\DeclareMathOperator{\aroperator}{ar}
\DeclareMathOperator{\doperator}{d}
\DeclareMathOperator{\qoperator}{q}
\DeclareMathOperator{\roperator}{r}
\DeclareMathOperator{\linegraph}{L}

\newcommand{\arh}{\aroperator(\h)}
\newcommand{\deh}{\doperator_{\h}}
\newcommand{\rh}{\roperator(\h)}
\newcommand{\qh}{\qoperator(\h)}

%%%---------------------------------------------------------------------------

%%% Changer la largeur des adresses
% Jouer avec \hsize :
\makeatletter
\def\@setafterauthor{%
  \vglue3mm%
%  \hspace*{0pt}%
\begingroup\hsize=12.5cm\advance\hsize\abstractmarginL\raggedright%~ trop grand et dÃ©passait la largeur de l'abstract
\noindent
%\hspace*{\abstractmarginL}\begin{minipage}[t]{10cm}
   \leftskip\abstractmarginL
  \normalfont\Small
  \@afterauthor\par
\endgroup
\vskip2pt plus 3pt minus 1pt
}
\makeatother

%%%---------------------------------------------------------------------------

\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}

%%%---------------------------------------------------------------------------

\graphicspath{{./figures/}}

\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}

\newcommand*{\relabel}{\renewcommand{\labelenumi}{(\theenumi)}}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}\relabel}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}\relabel}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}\relabel}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}\relabel}
\let\oldforall\forall
\renewcommand*{\forall}{\mathrel{\oldforall}}

\title{About Berge--F\"uredi's conjecture on the chromatic index of hypergraphs}
\alttitle{Sur la conjecture de Berge--FÃ¼redi sur l'indice chromatique des hypergraphes}

\author{\firstname{Alain} \lastname{Bretto}}
\address{Universit\'e Caen Normandie, GREYC CNRS-UMR 6072, Caen, France}
\email{alain.bretto@info.unicaen.fr}

\author{\firstname{Alain} \lastname{Faisant}}
\address{Universit\'e Jean Monnet, ICJ UMR5208, CNRS, \'Ecole Centrale de Lyon, INSA Lyon, Universit\'e Claude Bernard Lyon 1, 42023 Saint-\'Etienne, France}
\email{faisant@univ-st-etienne.fr}

\author{\firstname{FranÃ§ois} \lastname{Hennecart}\IsCorresp}
\address[2]{Universit\'e Jean Monnet, ICJ UMR5208, CNRS, \'Ecole Centrale de Lyon, INSA Lyon, Universit\'e Claude Bernard Lyon 1, 42023 Saint-\'Etienne, France}
\email{francois.hennecart@univ-st-etienne.fr}

\subjclass{05C15}

\keywords{\kwd{Hypergraphs} \kwd{hyperedge coloring} \kwd{chromatic index}}
\altkeywords{\kwd{Hypergraphes} \kwd{coloration des hyperarÃªtes} \kwd{indice chromatique}}

\begin{abstract}
We prove that the chromatic index of a hypergraph $\mathcal{H}$ satisfies the {Berge--F\"uredi} 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\H{o}s--Faber--Lov\'asz} conjecture which deals with the coloring of a family of cliques that intersect pairwise in at most one vertex.
\end{abstract}

\begin{altabstract}
Nous montrons que l'indice chromatique d'un hypergraphe satisfait la borne conjecturÃ©e indÃ©pendamment par Berge et F\"uredi, $\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\'e maximum $\Delta(\mathcal{H})$. Ces rÃ©sultats fournissent des informations sur la conjecture de Erd\H{o}s, Faber and Lov\'asz qui traite de la coloration d'une famille de cliques se coupant deux Ã&nbsp; deux en au plus un sommet.
\end{altabstract}

\makeatletter
\def\cdr@preabstracthook{\par\smallskip}
\makeatother

\begin{document}

\maketitle

\vspace{-0.75em}

\section{Introduction}

Berge--F\"uredi's conjecture (cf.~\cite{BER1989,BER1997,FUR1986} and {Meyniel}, unpublished communication) extends to linear hypergraphs {Vizing}'s theorem on the chromatic index of graphs (see~\cite[Theorem~7.2.2]{BFH2022}). It asserts that the chromatic index of any linear hypergraph $\h=(V, E)$ without loop satisfies
\begin{equation}\label{eq1}
\qh\le\Ddeuxh+1.
\end{equation}
This bound was first conjectured around 1986. Since then, to our knowledge, only few advances have been made. It has been recently proved~\cite{ZHANGSKINNER2020} that~\eqref{eq1} holds whenever $\Ddeuxh\le 5$. In the present paper we obtain new conditional results where the antirank $\arh$ and the maximum degree $\Dunh$ are involved together with the maximum degree $\Ddeuxh$ of the $2$-section of $\h$.

If $\h$ is linear then $\Ddeuxh\le \abs{V}-1$. Hence bound~\eqref{eq1} implies {Erd\H os--Faber--Lov\'asz} conjecture asserting that $\qh\le \abs{V}$ for any linear hypergraph $\h$.

\section{Notation and statements}

Let $\h=(V,E)$ be a hypergraph. For $x\in V$ and $e\in E$, we let
\[
\degh(x)=\biggl\lvert\bigl\{a\in E\,:\, x\in a\bigr\}\biggr\rvert,\quad
\deh(e)=\biggl\lvert\bigl\{a\in E\smallsetminus\{e\}\,:\, a\cap e\ne\varnothing\bigr\}\biggr\rvert,
\]
be the \emph{degree of vertex $x$} and the \emph{degree of hyperedge $e$} in $\h$, respectively. Then, we define respectively the \emph{rank}, the \emph{antirank}, the \emph{maximum degree} and the \emph{minimum degree} of $\h$ by
\[
\rh=\max_{e\in E}\abs{e},\quad
\arh=\min_{e\in E}\abs{e},\quad
\Dunh=\max_{x\in V}\degh(x),\quad
\delta(\h)=\min_{x\in V}\degh(x).
\]
A \emph{loop} in a hypergraph $\mathcal{H}$ is a hyperedge $e$ such that $\abs{e}=1$.

The \emph{$2$-section} of $\h=(V,E)$ is the loopless multigraph $[\h]_2=(V,A)$ with $k$ many edges between $x,y\in V$, $x\ne y$, if there are $k$ hyperedges in $\h$ containing both $x$ and~$y$. We have
\begin{equation}\label{eqn0}
\Ddeuxh\ge \bigl(\arh-1\bigr)\Dunh.
\end{equation}
The \emph{chromatic index} of $\h$, denoted by $\qh$, is the least integer $q$ such that there exists a map $c\colon E\to\{1,2,\dots,q\}$ satisfying
\[
\forall e,e'\in E,\; \bigl(c(e)=c(e')\implies e\cap e' =\varnothing \;\text{ or }\; e=e'\bigr).
\]
The map $c$ is called a \emph{hyperedge-coloring} of $\h$ and the image of $E$ through $c$ forms the set of \emph{colors}.

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

Recently it has been established that if $\h$ is a linear hypergraph satisfying
\begin{equation}\label{arh}
\arh\ge \sqrt{\abs{V}},
\end{equation}
then $\qh\le \abs{V}$ (cf.~\cite{WANG2024}). This upper bound has been improved in~\cite{BFH2024} where it is shown that under the same hypotheses on $\h$, then~\eqref{eq1} actually holds. In this note we show that condition~\eqref{arh} can be weakened by proving the following sharper result.

\begin{theo}\label{thm1}
Let $\h=(V,E)$ be a loopless hypergraph such that $\arh \ge \sqrt{\Ddeuxh+1}$. Then $\qh\le \Ddeuxh+1$.
\end{theo}

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

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

\begin{theo}\label{thm2}
Let $k\ge2$ and $\h=(V,E)$ be a $k$-uniform and $(k+1)$-regular linear hypergraph. Then $\qh\le \Ddeuxh+1$.
\end{theo}

The following corollary will be derived from Theorem~\ref{thm1}.

\begin{coro}\label{cor3}
Let $\mathcal{H}=(V, E)$ be a loopless hypergraph such that
\begin{equation}\label{eqcor1}
\Dunh\leq \sqrt{\Ddeuxh+1}+1.
\end{equation}
Then $\qh\leq \Ddeuxh+1.$
\end{coro}

\section{Proof of Theorem~\ref{thm1}}

In~\cite{BFH2024} we exploited the notion of critical hyperedge. A hyperedge $e$ is said \emph{critical} if $\qoperator(\h\smallsetminus e)=\qh-1$. Hypergraph $\h$ is a \emph{critical hypergraph} if all its hyperedges are critical. Since the addition of $e$ to $\h\smallsetminus e$ needs a new color, $e$ must intersect every color of $\h\smallsetminus e$. So we have the following.

\begin{lemm}[{\cite[Lemma~3.2]{BFH2024}}]\label{lemkey}
Let $\h=(V,E)$ be a hypergraph without loop and $e\in E$ be a critical hyperedge. Then $\qh-1\le \deh(e)$.
\end{lemm}

We may assume that $\h$ is connected and critical since $\aroperator(\h')\ge \arh$ and $\Delta\bigl([{\h}']_2\bigr)\le \Delta\bigl([{\h}]_2\bigr)$ for any partial hypergraph ${\h}'$ of ${\h}$. Let $e\in E$ be of minimum cardinality $k\coloneqq\arh$. We have
\begin{equation}\label{eqdhe}
\deh(e)=\sum_{\substack{a\in E\smallsetminus\{e\}\\a\cap e\ne\varnothing}}1\le \sum_{a\in E\smallsetminus\{e\}}\abs{a\cap e} =\sum_{x\in V}\sum_{\substack{a\in E\smallsetminus\{e\}\\a\ni x}}1 =\sum_{x\in e}\bigl(\degh(x)-1\bigr),
\end{equation}
and equality occurs when $\h$ is linear. Then by Lemma~\ref{lemkey} we get
\[
\qh-1=\qoperator({\h}\smallsetminus e)\le \deh(e) \le k\bigl(\Delta({\h})-1\bigr)=(k-1)\Delta({\h})-\bigl(k-\Delta({\h})\bigr),
\]
so
\begin{equation}\label{eq25}
\qh\le \Ddeuxh+1 -\bigl(k-\Dunh\bigr).
\end{equation}
Our hypothesis implies $\Ddeuxh\le k^2-1$. We distinguish two cases.
\begin{itemize}
\item If $\Ddeuxh&lt;k^2-1$ we get by~\eqref{eqn0} that $\Dunh&lt;k+1$ thus $\Dunh\le k$, yielding the required upper bound for $\qh$ by~\eqref{eq25}.
\item Assume that $\Ddeuxh=k^2-1$. We thus have to prove that $\qh\le k^2$. If there exists $e\in E$ such that $\abs{e}=k$ and $\deh(e)\le k^2-1$ then $\qh\le \deh(e)+1\le k^2$ by Lemma~\ref{lemkey} and we are done. Otherwise
\begin{equation}\label{eqn1}
\deh(e)\ge k^2\quad\text{ for any hyperedge $e$ of cardinality $k$.}
\end{equation}
We shall see that $\h$ is a very special hypergraph.
\begin{itemize}
\item Let $e\in E$ be of cardinality $k$. By~\eqref{eqn0} we have $\Dunh\le k+1$, thus by~\eqref{eqn1} and~\eqref{eqdhe} we get
\[
k^2\le \deh(e)\le\sum_{x\in e}\bigl(\degh(x)-1\bigr)\le k\bigl(\Dunh-1\bigr)
\le k(k+1-1)=k^2.
\]
We infer
\begin{equation}\label{eqn2}
\deh(e)=k^2\quad \text{ and }\quad
\degh(x)-1=k\quad \text{ for any $x\in e$.}
\end{equation}
\item Let $a\in E$ such that $a\cap e\ne \varnothing$. Let $x\in a\cap e$. We have
\begin{equation*}
\begin{split}
k^2-1=\Ddeuxh\ge \deg_{[\h]_2}(x)&amp;=\sum_{\substack{b\in E\\b\ni x}}\bigl(\abs{b}-1\bigr)\\
&amp;=\abs{a}-1+\sum_{\substack{b\in E\smallsetminus\{a\}\\b\ni x}}\bigl(\abs{b}-1\bigr)\\
&amp;\ge \abs{a}-1+\bigl(\degh(x)-1\bigr)(k-1)\\
&amp;= \abs{a}-1+k(k-1)\\
&amp;\ge k^2-1,
\end{split}
\end{equation*}
giving $\abs{a}=k$.
\item Since $\h$ is connected we infer that $\abs{a}=k$ for any $a\in E$. Hence $\h$ is $k$-uniform and $(k+1)$-regular. By~\eqref{eqdhe} and~\eqref{eqn2}, we have $\abs{a\cap e}=1$ whenever $a\cap e\ne\varnothing$. Thus $\h$ is linear. The proof will be completed when Theorem~\ref{thm2} will be established.
\end{itemize}
\end{itemize}

\section{Proof of Theorem~\ref{thm2}}

By assumption we have
\begin{equation}\label{eq21}
k\abs{e}=(k+1)\abs{V},\quad
\Ddeuxh=k^2-1\quad\text{ and } \quad \forall e\in E,\ d_{\h}(e)=k^2.
\end{equation}
Since $\h$ is linear, its \emph{line-graph} $\linegraph({\h})$ is the simple graph whose vertices are hyperedges of ${\h}$ and such that there is an edge between $e,e'\in E$, $e\ne e'$, if $e\cap e'\ne \varnothing$. We have $\deg_{\linegraph({\h})}(e)=\deh(e)$ for any $e\in E$.

By~\eqref{eq21}, each vertex $e$ of $\linegraph(\h)$ has degree $\deg_{\linegraph(\h)}(e)=k^2$. Hence $\linegraph(\h)$ is $k^2$-regular. Since $\qh$ coincides with $\chi\bigl(\linegraph(\h)\bigr)$, namely the chromatic number of the simple graph $\linegraph(\h)$, we infer from Brooks' theorem (see~\cite[Theorem~7.1.9, p.~238]{BFH2022}) that either
\[
\qh\le \Delta\bigl(\linegraph(\h)\bigr)=k^2=\Ddeuxh+1
\]
or $\linegraph(\h)$ is complete or an odd-length cycle. If $\linegraph(\h)$ were a complete graph, we would have $\abs{e}=k^2+1$ implying by~\eqref{eq21} that $(k+1)$ divides $k(k^2+1)$, which gives a contradiction since $k\ge2$. If $\linegraph(\h)$ were a cycle, we would have $d_{\h}(e)=\deg_{\linegraph(\h)}(e)=2$ for any $e\in E$, a contradiction. This ends the proof of Theorem~\ref{thm2}.

\section{Proof of Corollary~\ref{cor3}}

Let ${\h}'=(V,E')$ be a critical partial hypergraph of ${\h}$ such that $\qoperator({\h}')=\qh$.
\begin{itemize}
\item If $\aroperator({\h}')\ge\sqrt{\Delta\bigl([\h']_2\bigr)+1}$ we infer from Theorem~\ref{thm1} that
\[
\qh=\qoperator({\h}')\le \Delta\bigl([\h']_2\bigr)+1\le \Ddeuxh+1.
\]
\item If $\aroperator({\h}')&lt;\sqrt{\Delta\bigl([\h']_2\bigr)+1}$ then we take $e\in E'$ such that $\abs{e}=\aroperator({\h}')$. By Lemma~\ref{lemkey} and using~\eqref{eqdhe} with $\h'$ in place of $\h$, we get
\begin{equation*}
\begin{split}
\qh-1=\qoperator({\h}')-1&amp;\le \doperator_{\h'}(e)\\
&amp;\le \sum_{x\in e}\bigl(\deg_{{\h}'}(x)-1\bigr)\\
&amp;\le \abs{e}\bigl(\Delta({\h}')-1\bigr)\\
&amp;= \aroperator({\h}')\bigl(\Delta({\h'})-1\bigr)\\
&amp;&lt; \sqrt{\Delta\bigl([\h']_2\bigr)+1}\bigl(\Delta({\h'})-1\bigr)\\
&amp;\le \sqrt{\Ddeuxh+1}\bigl(\Delta({\h})-1\bigr)\\
&amp;\le \Ddeuxh+1
\end{split}
\end{equation*}
by~\eqref{eqcor1}. Hence $\qh\leq \Ddeuxh+1$ as wanted.
\end{itemize}

\section{Remarks and questions}

\subsection{}\label{rk81}
We should notice that when $\arh&gt;\sqrt{\Ddeuxh+1}$ then the desired bound $\qh\le
\Ddeuxh+1$ can be equally deduced from the greedy algorithm for coloring hyperedges (see for instance~\cite[p.~586]{DVOR2000}) which yields
\[
\qh\le \max_{\rh\ge k\ge \arh} k\Biggl\lfloor\frac{\Ddeuxh}{k-1}-1\Biggr\rfloor+1.
\]
Here we use a different approach which allows us to solve in addition the equality case $\arh=\sqrt{\Ddeuxh+1}$.

\subsection{}\label{rk82}
When the maximum degree $\Dunh$ satisfies $\Dunh &gt; \sqrt{\Ddeuxh+1}+1$, Corollary~\ref{cor3} is no longer usable. However at the cost of an additional condition on the rank $\rh=\max_{e\in E}\abs{e}$, we can notice that~\eqref{eq1} remains valid for linear hypergraphs $\h$. Let $\delta_2\coloneqq\sqrt{\Ddeuxh}$ and assume that
\begin{align*}
\rh&amp;=\delta_2-u,\; u&gt;0,\\
\Dunh &amp;= \delta_2 +1+v,\; v&gt;0.
\end{align*}
Then
\[
\qh= \chi\bigl(\linegraph(\h)\bigr)\leq \Delta\bigl(\linegraph(\h)\bigr)+1 \leq \rh\bigl(\Dunh-1\bigr)+1=(\delta_2-u)(\delta_2+v)+1.
\]
Thus~\eqref{eq1} holds whenever $(v-u)\delta_2\le uv$, that is $\frac1u\le \frac1v+\frac1{\delta_2}$.

\subsection{}
If $\h$ is supposed linear, in the \emph{extremal case} $\Ddeuxh=\abs{V}-1$, $\arh=\abs{V}^{1/2}$ in Theorem~\ref{thm1} the authors obtained in~\cite{BFH2024} a much better upper bound for $\qh$, namely $\qh\le \frac12(\Ddeuxh+1+\sqrt{\Ddeuxh+1})+1$. How can the upper bound for $\qh$ be improved under the sole condition~$\arh = \sqrt{\Ddeuxh+1}$?

\subsection{}
Theorem~\ref{thm2} deals with $k$-uniform and $d$-regular linear hypergraphs when $d=k+1$ and provides the required bound~\eqref{eq1}. For general $k,d$ satisfying $k\le d-2$, the line-graph $\linegraph(\h)$ is $k(d-1)$-regular and Brooks' theorem provides the (non sufficiently sharp) inequality $\qh=\chi\bigl(\linegraph(\h)\bigr)\le \Delta\bigl(\linegraph(\h)\bigr)=k(d-1)$ while $\Ddeuxh=d(k-1)$.

\subsection{}
More generally let $\h$ be a $k$-uniform linear hypergraph with $k\ge2$ and set $\delta_2\coloneqq\sqrt{\Ddeuxh}$. Then~\eqref{eq1} holds if at least one of the following conditions is satisfied:
\begin{enumerate}
\item $k=2$: Vizing's theorem (see~\cite[Theorem~7.2.2, p.~249]{BFH2022});
\item $k\ge\sqrt{\Ddeuxh+1}$: Theorem~\ref{thm1};
\item $\Ddeuxh=k^2$ which implies \smash{$\Dunh\le \sqrt{\Ddeuxh}+1$}: Corollary~\ref{cor3};
\item $3\le k &lt;\delta_2$ and $\frac1{\delta_2-k}\le \frac1{\Dunh-\delta_2-1}+\frac{1}{\delta_2}$: see Section~\ref{rk82}.
\end{enumerate}
In order to solve Berge--F\"uredi's conjecture for all linear uniform hypergraphs, it thus remains to consider the case where
\[
3\le k&lt;\delta_2&lt;\Dunh-1 \quad\text{ and }\quad
\frac1{\delta_2-k} &gt; \frac1{\Dunh-\delta_2-1}+\frac{1}{\delta_2}.
\]
We may likewise ask the following question: is Berge--F\"uredi's conjecture in all its generality implied by its validity for linear uniform hypergraphs?

\section*{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.

\printbibliography
\end{document}
</pre></body></html>