There are no edge-chromatic 4-critical graphs of order 12

✍ Scribed by S.A. Choudum; K. Kayathri

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 269 KB
• Volume: 141
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0208-l

✦ Synopsis

We prove that there are no edge-chromatic 4-critical graphs of order 12.

1. Introduction

A well-known theorem of Vizing [4] states that: ifG is a simple graph with maximum degree A, then the edge chromatic number z'(G) of G is A or A + 1. A graph G is said to be of class 1 if z'(G) = A, and it is said to be of class 2 if Z'(G) = A + 1. G is said to be (edge-chromatic) critical if it is connected, class 2, and Z'(G-e)< z'(G) for every edge e. A critical graph G with maximum degree A is called A-critical. It is easy to construct critical graphs of odd order but not of even order. The smallest known critical graph of even order is 4-critical and has order 18: it is due to M.A. Fiol Isee Yap [6, p. 35] ). It is also known that there are no critical graphs of even order less than 12 and that there are no 3-critical graphs of order 12 or 14. Motivated by this and the fact that smallest counter examples usually possess interesting properties, Yap [6, p. 49] has posed the following:

Problem. Does there exist a critical graph of order 12, 14, or 167 Our aim in this paper is to show that there are no 4-critical graphs of order 12. Let G=(V,E) be a graph with n vertices, m edges, maximum degree A(G) and minimum degree 6(G). IfA = {vl, vz ..... vv} ~_ Vand deg~(vl)=di, then gc;(A) denotes the sequence dl, d2 ..... d v. If S and T are disjoint subsets of V(G), then [S, T]~; (or IS, T]) denotes the set of edges with one end in S and the other in T: [S]~ or [S] * Corresponding author.