期刊论文

Jiang, Suyun

英文

Discrete Mathematics

0012-365X

2019

342

6

1613-1623

10.1016/j.disc.2019.02.014

NSFC, ChinaNational Natural Science Foundation of China (NSFC) [11871239, 11671232, 61501208, 11571096, 61373019, 11671186]

本校为其他机构

Given a graph $G$, denote by $\Delta$, $\bar{d}$ and $\chi^\prime$ the maximum degree, the average degree and the chromatic index of $G$, respectively. A simple graph $G$ is called {\it edge-$\Delta$-critical} if $\chi^\prime(G)=\Delta+1$ and $\chi^\prime(H)\le\Delta$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is edge-$\Delta$-critical, then $\bar{d}\geq \Delta-1+ \frac{3}{n}$. We show that $$ \begin{displaystyle} \avd \ge \begin{cases} 0.69241\D-0.15658 \quad\,\: \mbox{ if } \Delta\geq 66, 0.69392\D-0.20642\quad\;\,\mbox{ if } \Delta=65, \mbox{ and } 0.68706\...