Name
Abstract | ||
|---|---|---|
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+3n. We prove that for any edge-Δ-critical graph G, d̄(G)≥min22Δ(G)−3−222+1,3Δ(G)4−2, that is, d¯(G)≥34Δ(G)−2ifΔ(G)≤75;22Δ(G)−3−222+1≈0.7388Δ(G)−1.153ifΔ(G)≥76.This result improves the best known bound 23(Δ(G)+2) obtained by Woodall in 2007 for Δ(G)≥41. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.disc.2019.02.014 | Discrete Mathematics |
Keywords | Field | DocType |
Edge-k-coloring,Edge-critical graphs,Vizing’s adjacency lemma | Prime (order theory),Adjacency list,Discrete mathematics,Graph,Edge coloring,Combinatorics,Chromatic scale,Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
342 | 6 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yan Cao | 1 | 14 | 4.30 |
| Guantao Chen | 2 | 107 | 25.00 |
| Suyun Jiang | 3 | 0 | 1.01 |
| Huiqing Liu | 4 | 18 | 4.92 |
| Fuliang Lu | 5 | 5 | 6.07 |