No label defined (Q3976633)
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 19203
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 19203 |
Statements
26 June 1992
0 references
overfull graph
0 references
0.8687615990638733
0 references
0.8618836402893066
0 references
0.860209047794342
0 references
0.8356475830078125
0 references
[For the entire collection see Zbl 0734.00014.] We say a graph \(G\) is overfull if size of \(G\) over \(\lfloor{1\over 2} \hbox { order of } G\rfloor\) is greater than maximum vertex degree \(h(G)\) of \(G\). A subgraph \(H\) of \(G\) is called a \(h(G)\)-overfull subgraph of \(G\) if \(H\) is overfull and \(h(H)=h(G)\). There is stated the following conjecture and five striking implications (without proofs) of it. A planar graph \(G\) has chromatic index \(h(G)\) iff \(G\) contains no \(h(G)\)- overfull subgraph.
0 references
