On the circumference of class 2 graphs

Abstract

A graph is Δ-critical if it is connected, has maximum degree Δ, chromatic index Δ + 1, and deleting any edge results in a graph of smaller chromatic index. Vizing has shown that the circumference of a Δ-critical graph G is at least Δ + 1. We characterize those Δ-critical graphs of circumference exactly Δ + 1. We also obtain lower bounds on the circumference of Δ-critical graphs of girth at least g (g ≥ 4). Using these results, we show that a class 2 graph with maximum degree Δ and girth g has circumference at least (Δ - 1)(g - 2) + 2 if g ≤ 4, g ≥ 10 or Δ ≤ 3, and circumference at least (Δ - 1)(g - 3) + 2 if 5 ≤ g ≤ 9 and Δ ≥ 4.