Chromatic-index-critical graphs of orders 11 and 12
type: Item
instance of: scholarly article
title: Chromatic-index-critical graphs of orders 11 and 12
zbMATH Open document ID: 0918.05050
author: Gunnar Brinkmann
author: Eckhard Steffen
published in: European Journal of Combinatorics
publication date: 1999-08-19T00:00:00Z
review text: A simple graph \(G\) with maximum vertex degree \(\Delta\) is called \(\Delta\)-critical (or chromatic-index-critical) if the chromatic index \(\chi'(G)\) of \(G\) is \(\Delta+1\) and \(\chi'(G-e)=\Delta\) for any edge \(e\) of \(G\). A \(\Delta\)-critical graph \(G=(V,E)\) having at most \(\Delta\left\lfloor{| V|\over 2}\right\rfloor\) edges is said to be non-trivial. \textit{L. W. Beineke} and \textit{S. Fiorini} [Discrete Math. 16, 109-121 (1976; Zbl 0344.05121)] proved that there are no chromatic-index-critical graphs of even order at most 10. In this paper it is shown that there are no chromatic-index-critical graphs of order 12. (A shorter proof that there are no chromatic-index-critical graphs of order 10 is given in a forthcoming paper by Z. X. Song and the reviewer.) It was known that the graph obtained by deleting any vertex from the Petersen graph is the only non-trivial odd order chromatic-index-critical graph of order at most 10. The authors, using computers, show that there are precisely two non-trivial chromatic-index-critical graphs of order 11. The previous known results together with the new results proved in this paper imply that there are precisely three non-trivial chromatic-index-critical graphs of order at most 12.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1248163
zbMATH Keywords: chromatic index
zbMATH Keywords: chromatic-index-critical graphs
reviewed by: H. P. Yap
MaRDI profile type: Publication
OpenAlex ID: W1988405842
DOI: 10.1006/EUJC.1998.0254
Recommended article: Chromatic-index-critical graphs of orders 13 and 14
Recommended article: Chromatic index critical graphs of even order with five major vertices
Recommended article: Q4713915
Recommended article: There are no edge-chromatic 4-critical graphs of order 12
Recommended article: Q4351068
Recommended article: Chromatic-index critical multigraphs of order 20
Recommended article: On the existence of two non-neighboring subgraphs in a graph
Recommended article: Edge‐chromatic critical graphs and the existence of 1‐factors
Recommended article: Q3538561
Recommended article: On the size of critical graphs with small maximum degree
description: scientific article; zbMATH DE number 1248163