期刊论文

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]

本校为其他机构

Let G be a simple graph, and let Δ(G), d¯(G) and χ ′ (G) denote the maximum degree, the average degree and the chromatic index of G, respectively. We called G edge-Δ-critical if χ ′ (G)=Δ(G)+1 and χ ′ (H)≤Δ(G) for every proper subgraph H of G. Vizing in 1968 conjectured that if G is an edge-Δ-critical graph of order n, then d¯(G)≥Δ(G)−1+[Formula presented]. We prove that for any edge-Δ-critical graph G, d̄(G)≥min[Formula presented],[Formula presented]−2, that is, d¯(G)≥[Formula presented]Δ(G)−2ifΔ(G)≤75;[Formula prese...