There are no edge-chromatic 4-critical graphs of order 12
type: Item
instance of: scholarly article
title: There are no edge-chromatic 4-critical graphs of order 12
zbMATH Open document ID: 0826.05028
DOI: 10.1016/0012-365X(93)E0208-L
author: K. Kayathri
author: S. A. Choudum
published in: Discrete Mathematics
publication date: 1995-11-26T00:00:00Z
review text: Let \(\chi'(G)\) and \(\Delta(G)\) denote respectively the chromatic index and the maximum degree of the vertices of a simple graph \(G\). Vizing's theorem says that \(\chi'(G)= \Delta(G)\) or \(\Delta(G)+ 1\). If \(\chi'(G)= \Delta(G)+ i- 1\), \(i= 1,2\), then \(G\) is said to be class \(i\). If \(G\) is a connected graph having \(\Delta(G)= \Delta\) and \(G\) is of class 2 such that \(\chi'(G- e)< \chi'(G)\) for any edge \(e\) of \(G\), then \(G\) is said to be \(\Delta\)-critical. Even order \(\Delta\)-critical graphs are rare. The smallest known 4-critical even order graph has 18 vertices. It has been proved that there are no 3-critical graphs of even order less than 16. In this paper the authors prove that there are no 4-critical graphs of order 12. This gives a partial answer to a question raised by the reviewer in the book [Some topics in graph theory (1986; Zbl 0588.05002)]. Misprint: In the proof of (R8), the edge \(e\) should be \(vw\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 778525
zbMATH Keywords: edge-colourings
zbMATH Keywords: chromatic index
zbMATH Keywords: maximum degree
zbMATH Keywords: \(\Delta\)-critical graphs
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: On small graphs critical with respect to edge colourings
cites work: Q3853641
cites work: Q5558480
cites work: Q3715121
description: scientific article; zbMATH DE number 778525