Reverse class critical multigraphs
type: Item
instance of: scholarly article
title: Reverse class critical multigraphs
zbMATH Open document ID: 0643.05031
DOI: 10.1016/0012-365X(88)90059-3
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: Let be \(G=G(V,E)\) a loopless multigraph with the maximum degree \(\Delta\) (G) and the chromatic index \(\chi'(G).\) If \(\Delta(G)=\chi'(G)\), then G is said to be Class 1, and otherwise G is Class 2. In this note are considered multigraphs with the property that upon the removal of any vertex the chromatic class rises. And a multigraph is called reverse class critical (exactly vertex reverse class critical or VRC-critical multigraph) if G is Class 1 but \(G\setminus v\) is Class 2 for each \(v\in V(G).\) It is well-known that \(K_{2p}\) is Class 1 and it is shown that also \(K_{2p}^{(r)}\) is Class 1 for all \(r\geq 1\) (let \(K_ n^{(r)}\) denote the graph obtained from \(K_ n\) by replicating each edge r times). By using this result those VRC-critical multigraphs are characterized which have at least two vertices of degree r(n-1) [Theorem 3]. And by applying Theorem 3 there follows a characterization of VRC- critical simple graphs G if holds that \(| V(G)|\) is even. In this case a lower bound for \(| E(G)|\) is deduced in Theorem 4.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 4047753
zbMATH Keywords: characterization of multigraphs
author: A. J. W. Hilton
author: P. D. jun. Johnson
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Q3853641
cites work: A generalization of Plantholt's theorem
cites work: Graphs which are vertex‐critical with respect to the edge‐chromatic class
full work available at URL: 0012-365x(88)90059-3
OpenAlex ID: W2053245821
description: scientific article; zbMATH DE number 4047753