On the size of edge-chromatic critical graphs
type: Item
instance of: scholarly article
title: On the size of edge-chromatic critical graphs
zbMATH Open document ID: 0807.05032
DOI: 10.1007/BF02986658
author: K. Kayathri
published in: Graphs and Combinatorics
publication date: 1994-09-26T00:00:00Z
review text: Let \(G\) be a graph with \(n\) vertices, \(m\) edges, edge-chromatic number \(\chi'(G)\) and maximum degree \(\Delta\). A conjecture of V. G. Vizing states that if \(\chi'(G)= \Delta+ 1\), but \(\chi'(G- e)< \chi'(G)\) for all edges \(e\) of \(G\), then \(m\geq {1\over 2}(n(\Delta- 1)+ 3)\). This inequality was proved for \(\Delta\leq 4\). In this paper the conjecture is proved for \(\Delta= 5\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 644731
zbMATH Keywords: edge-chromatic critical graphs
zbMATH Keywords: Vizing conjecture
zbMATH Keywords: edge-chromatic number
reviewed by: Raffaele Scapellato
MaRDI profile type: Publication
cites work: On small graphs critical with respect to edge colourings
cites work: Chromatic index critical graphs of order 9
cites work: Some remarks on a paper by Vizing on critical graphs
cites work: On critical graphs with chromatic index 4
cites work: Q5558480
cites work: Q5564127
cites work: On graphs critical with respect to edge-colourings
cites work: Q3715121
cites work: Corrigendum to: On graphs critical with respect to edge-colourings
description: scientific article; zbMATH DE number 644731