The size of edge chromatic critical graphs with maximum degree 6

Abstract

Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph ${{G}} = ({{V}}, {{E}})$ with maximum degree $\Delta$ , $|{{E}}| \geq {{{1}}\over {{2}}}\{(\Delta {{- 1}})|{{V}}| + {{3}}\}$ . This conjecture has been verified for $\Delta \leq {{5}}$ . In this article, by applying the discharging method, we prove the conjecture for $\Delta = {{6}}$ . © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 149–171, 2009