On the size of edge-chromatic critical graphs (Q1334940)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the size of edge-chromatic critical graphs |
scientific article; zbMATH DE number 644731
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the size of edge-chromatic critical graphs |
scientific article; zbMATH DE number 644731 |
Statements
On the size of edge-chromatic critical graphs (English)
0 references
26 September 1994
0 references
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\).
0 references
edge-chromatic critical graphs
0 references
Vizing conjecture
0 references
edge-chromatic number
0 references
