Premium
Overfull conjecture for graphs with high minimum degree
Author(s) -
Plantholt Michael
Publication year - 2004
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.20013
Subject(s) - combinatorics , mathematics , degree (music) , conjecture , graph , chromatic scale , order (exchange) , edge coloring , discrete mathematics , induced subgraph , graph power , line graph , vertex (graph theory) , physics , finance , economics , acoustics
Chetwynd and Hilton showed that any regular graph G of even order n which has relatively high degree $\Delta (G)\,\ge\,((\sqrt{7}- 1)/2)\, n$ has a 1‐factorization. This is equivalent to saying that under these conditions G has chromatic index equal to its maximum degree $\Delta(G)$ . Using this result, we show that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree $\delta(G)\,\ge\,(\sqrt{7}/3)\,n$ has chromatic index equal to its maximum degree providing that G does not contain an “overfull” subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 73–80, 2004