Reverse class critical multigraphs (Q1101459)

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.