The average degree of an edge‐chromatic critical graph II
Douglas R. Woodall · Journal of Graph Theory · 2007
Abstract A graph G with maximum degree Δ and edge chromatic number $\chi\prime({G}) > \Delta$ is edge‐Δ‐critical if $\chi\prime{(G-e)} = \Delta$ for every edge e of G. It is proved that the average degree of an edge‐Δ‐critical graph is at least ${2\over 3}{(\Delta+1)}$ if $\Delta \geq 2$ , at least ${2\over 3}\Delta + 1$ if $\Delta \geq 8$ , and at least ${2\over 3}(\Delta + 2)$ if $\Delta \geq 15$ . For large Δ, this improves on the best bound previously known, which was roughly ${1\over 2}(\Delta+\sqrt{2\Delta})$ . © Wiley Periodicals, Inc. J. Graph Theory 56: 194–218, 2007