\(K_ 5\) is the only double-critical 5-chromatic graph
type: Item
instance of: scholarly article
title: \(K_ 5\) is the only double-critical 5-chromatic graph
zbMATH Open document ID: 0613.05022
DOI: 10.1016/0012-365X(87)90242-1
author: Michael Stiebitz
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: A connected graph G is called double-critical if the chromatic number of G decreases by 2 when any two adjacent vertices of G are deleted. \textit{L. Lovász} [Theory of Graphs, Proc. Colloquium Tihany, Hungary 1966, 231- 236 (1968; Zbl 0157.312)] conjectured that \(K_ n\), the complete graph of order n, is the only double-critical graph having chromatic number n. This conjecture can be easily verified for \(n\leq 4\). The present author gives a nice, short proof of this conjecture for the case \(n=5\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3991528
zbMATH Keywords: chromatic critical
zbMATH Keywords: double-critical graph
zbMATH Keywords: chromatic number
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: Q5537559
cites work: Q3924234
cites work: Q3880849
Recommended article: Q4206747
Recommended article: Q4900077
Recommended article: \(k\)-critical graphs in \(P_5\)-free graphs
Recommended article: On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
Recommended article: Some results on \(k\)-critical \(P_5\)-free graphs
Recommended article: On the size of edge chromatic 5-critical graphs
Recommended article: A Note on k-Colorability of P 5-Free Graphs
Recommended article: A (5,5)-Colouring of Kn with Few Colours
Recommended article: Q4639771
description: scientific article; zbMATH DE number 3991528