.13-order Color Index Critical Graphs

In 1974, the critical graph conjecture was posed by I.T.Jackobsen: There are no critical graphs of even order. Five years later, M.K.Gol'dberg constructed an infinite family of 3-critical graphs of even order. In 1980, M.A.Fiol independently found the counterexample to the critical graph conjecture. He obtained two 4-critical graphs of order 18 and 30. From this, H.P.Yap posed the following problem:Problem Does there exist a critical graph of even order n where 12 ≤ n ≤ 16?With the aid of computer, G.Brinkmann and E.Steffen proved that there are no criticalgraphs of order 12. Limin Zhang also proved this result using the properties of chromatic index critical graph. In order to determine whether exist chromatic index critical graph of order 14, we should determine chromatic index critical of order 13 at first. Therefore, the aim of this paper is to determine all critical graphs of order 13. Following are the main results of the thesis:1. There are only 14 critical graphs of order 13 having degree-list 2³3¹⁰.2. A 2-connected graph of order 13 is 3-critical if and only if its degree-list is 2³3¹² except it contains a critical subgraph having degree-list 2³3⁶,2³3⁸ or 2³3¹⁰.3. A 2-connected graph of order 13 is 4-critical if and only if e(G) = 25 except it contains a critical subgraph having degree-list 3²4³,3²4⁵ or 3²4⁷.4. A 2-connected graph of order 13 is 5-critical if and only if e(G) = 31 except it contains a critical subgraph having degree-list 345⁵ or 4³5⁴.5. Let △≥ 5. A 2-connected graph of order 13 is △-critical if and only if e(G) = 6△+ 1.