Premium
Chromatic‐index critical multigraphs of order 20
Author(s) -
Grünewald Stefan
Publication year - 2000
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/(sici)1097-0118(200004)33:4<240::aid-jgt5>3.0.co;2-r
Subject(s) - multigraph , mathematics , combinatorics , critical graph , conjecture , edge coloring , graph , order (exchange) , chromatic scale , degree (music) , constant (computer programming) , graph theory , discrete mathematics , graph power , physics , computer science , line graph , finance , economics , acoustics , programming language
A multigraph M with maximum degree Δ( M ) is called critical, if the chromatic index χ′( M ) > Δ( M ) and χ′( M − e ) = χ′( M ) − 1 for each edge e of M . The weak critical graph conjecture [1, 7] claims that there exists a constant c > 0 such that every critical multigraph M with at most c · Δ( M ) vertices has odd order. We disprove this conjecture by constructing critical multigraphs of order 20 with maximum degree k for all k ≥ 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 240–245, 2000