On the Girth of Graphs Critical with Respect to Edge-Colourings
Stanley Fiorini · Bulletin of the London Mathematical Society · 1976
A graph G with maximum valency r is called critical if r + 1 colours are needed for an edgecolouring, but every proper subgraph requires at most r. In this note we consider the minimum order f(r, g) of a critical graph of maximum valency r and girth g. We show that f(r, 3) = r+1 or r+2 according as r is even or odd, f(r, 4) = 2r+1,f(3, 5) = 9 and f(3, 6) = 15.