The size of edge chromatic critical graphs with maximum degree 6
- 27 August 2008
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 60 (2) , 149-171
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
Keywords
This publication has 9 references indexed in Scilit:
- Chromatic-index-critical graphs of orders 13 and 14Discrete Mathematics, 2005
- Planar Graphs of Maximum Degree Seven are Class IJournal of Combinatorial Theory, Series B, 2001
- Every Planar Graph with Maximum Degree 7 Is of Class 1Graphs and Combinatorics, 2000
- Chromatic-Index-Critical Graphs of Orders 11 and 12European Journal of Combinatorics, 1998
- 3- and 4-critical graphs of small even orderDiscrete Mathematics, 1997
- On the size of Edge-Chromatic critical graphsGraphs and Combinatorics, 1994
- Chromatic index critical graphs of order 9Discrete Mathematics, 1983
- On small graphs critical with respect to edge colouringsDiscrete Mathematics, 1976
- On critical graphs with chromatic index 4Discrete Mathematics, 1974