We prove that a 2-connected graph of order 9 having maximum valency A 34 is chromatic index critical if and only if its valency-list is one of the following: 248, 3247 (except one graph), 258, 345 ', 4356, 26a, 356', 4267, 45266, 5465, 27', 367', 457', 46276, 52676, 56375, 6574, 57385, 6386, 627285, 67484 and 7683. This, together with known results, provide a complete catalogue of all chromatic index critical graphs of order ClO.
1. In-n
Let G be an undirected simple graph with vertex set V(G) and edge set E(G).
We write uu E E(G) if u, IJ E V(G) are adjacent in G.
For convenience, we often write UE G to mean that UE V(G) and we also write UVE G to mean that uv E E(G). The neighbourhood of u E V(G) is denoted by N(u) and the valency (degree) of u in G is denoted by d(u). If H is a subgraph of G, the valency of u E V(H) in H is denoted by &(u). We write IGl for the order of G, 0, for the null graph of order r, K, for the complete graph of order s, G U H for the union of two disjoint graphs G and H, 2G for the union of two disjoint copies of G, n, for the number of vertices of valency i in G, e(G) for the size of G and G for the complement of G. A near l-factor F of G having odd order II is a set of &(n -1) independent edges of G.
If v E V(G), we denote by G-v, the induced subgraph of G with vertex set V(G)\v. If uv E E(G), we denote by G -uv, the subgraph of G with vertex set V(G) and edge set E(G)\uv. If SE V(G), we denote by (S), the induced subgraph of G with vertex set S. Thus, for instance, (u, v, w) is the subgraph of G induced by the vertex set (u, v, W}E V(G). A (proper) colouring T of G is a.mapping from E(G) to {1,2,3, . . .} such that no two adjacent edges of G have the same image. The chromatic index x'(G) of G is the minimum cardinality of the image set of all possible colourings of G. A graph G is said to be k-colouruble if there is a colouring of G with the image set U,2, * * * , k). The well-known theorem of Vizing [7] says that if G is a graph with