A new lower bound on the order of a critical edge-chromatic graph with given small girth

Abstract

A graph is of class 2 if its edge-chromatic index is greater than its maximum degree. A class 2 graph G is critical edge-chromatic if the removal of any edge reduces its chromatic index. f(k, g) represents the minimum possible number of vertices in a critical graph of maximum degree k and girth g. We shall prove that 23 ≤ f(3, 7) ≤ 25.