标题:Average degrees of edge-chromatic critical graphs
作者:Cao, Yan; Chen, Guantao; Jiang, Suyun; Liu, Huiqing; Lu, Fuliang
作者机构:[Cao, Yan; Chen, Guantao] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.; [Chen, Guantao] Cent China Normal Univ, Sch Math & Stat, Wuh 更多
通讯作者:Jiang, SY;Jiang, SY
通讯作者地址:[Jiang, SY]Jianghan Univ, Inst Interdisciplinary Res, Wuhan 430056, Hubei, Peoples R China;[Jiang, SY]Shandong Univ, Sch Math, Jinan 250100, Shandong, 更多
来源:DISCRETE MATHEMATICS
出版年:2019
卷:342
期:6
页码:1613-1623
DOI:10.1016/j.disc.2019.02.014
关键词:Edge-k-coloring; Edge-critical graphs; Vizing's adjacency lemma
摘要:Let G be a simple graph, and let Delta(G), (d) over bar (G) and chi'(G) denote the maximum degree, the average degree and the chromatic index of G, respectively. We called G edge-Delta-critical if chi'(G) = Delta(G)-1- 1 and chi'(H) <= Delta(G) for every proper subgraph H of G. Vizing in 1968 conjectured that if G is an edge -A -critical graph of order n, then (d) over bar (G) >= Delta(G) - 1 + 3/n. We prove that for any edge-Delta-critical graph G, (D) over bar (G) >= min {2 root 2 Delta(G)-30 root 2/2 root 2_1, 3 Delta(G)/4-2}(n), that is,; (d) over bar (G) >= {3/4 Delta(G)-22 root 2 Delta(G) -3 -root 2/2 root + 1 approximate to 07388 Delta(G) - 10153 if Delta(G) <= 75; if Delta(G) >= 76.; This result improves the best known bound 2/31(Delta(G) + 2) obtained by Woodall in 2007 for Delta(G) >= 41. (C) 2019 Elsevier B.V. All rights reserved.
收录类别:SCOPUS;SCIE
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85062647413&doi=10.1016%2fj.disc.2019.02.014&partnerID=40&md5=88053794d99dcab08225a0b9688dc50e
TOP