Premium
The size of edge chromatic critical graphs with maximum degree 6
Author(s) -
Luo Rong,
Miao Lianying,
Zhao Yue
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20351
Subject(s) - conjecture , mathematics , combinatorics , chromatic scale , degree (music) , graph , critical graph , edge coloring , enhanced data rates for gsm evolution , delta , graph theory , discrete mathematics , physics , line graph , computer science , graph power , telecommunications , astronomy , acoustics
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom