Average degrees of edge-$\hat{I}”$-critical multigraphs

Abstract

Let $G$ be a loopless multigraph with maximum degree $\hat{I}”(G)$, average degree $\overline{d}(G)$, density $\hat{I}“(G)$, and chromatic index $\ddot{I}{‡}^{\prime }(G)$. A multigraph $G$ is called edge-$\hat{I}”$-critical if $\hat{I}”(G)=\hat{I}”$, $\ddot{I}{‡}^{\prime }(G)=\hat{I}”(G)+1$ and $\ddot{I}{‡}^{\prime }(H)\le \hat{I}”(G)$ for every proper subgraph $H\subset G$. Vizing conjectured that if $G$ is an edge-$\hat{I}”$-critical simple graph on $n$ vertices, then $\overline{d}(G)\ge \hat{I}”-1+\frac{3}{n}$. Motivated by this, we conjecture that every edge-$\hat{I}”$-critical multigraph $G$ satisfies $\overline{d}(G)\ge \frac{2\hat{I}”+2}{3}$, which is best possible. We first give a general lower bound in this direction. For any such graph $G$, \[ \overline{d}(G) \ge \begin{cases} \frac{\sqrt{17}-3}{2}(Δ+1) & \text{if } Δ\le 112;\\[4pt] \frac{Δ+\sqrt{2Δ-1}}{2} & \text{if } Δ\ge 113. \end{cases} \] This bound can be further improved under an additional condition on the multiplicity $\hat{I}¼$. In this case, \[ \overline{d}(G)\ge \min\left\{ \frac{2μΔ+2μ(2μ-1)}{4μ-1},\; \frac{\sqrt{17}-3}{2}(Δ+1) \right\}. \] We also confirm the conjecture for $\hat{I}”\in \{2,3,4,5,6,7,8\}$. As a consequence, Goldberg's conjecture~\cite{Goldberg1984} holds for $\hat{I}”(G)\in \{2,3,4,5\}$, that is, every multigraph $G$ with $\ddot{I}{‡}^{\prime }(G)\ge \hat{I}”(G)+1$ satisfies $\hat{I}“(G)\ge \hat{I}”(G)$.

18 pages, 1 table