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 the normal view instead:
scientific article; zbMATH DE number 644731
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.920108437538147
0 references
0.9016594886779784
0 references
0.8764945268630981
0 references
