No label defined (Q4250147)
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 1303525
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1303525 |
Statements
8 November 1999
0 references
colouring
0 references
probabilistic methods
0 references
0.8443445563316345
0 references
0.7982856035232544
0 references
Determining the minimum number of colours required to colour the vertices of a given graph so that every pair of adjacent vertices receive different colours is a notoriously difficult problem. In this paper a naive colouring procedure is examined, that consists of choosing a colour for each vertex, uncolouring those involved in a conflict, and recursively repeating this process on the uncoloured vertices. This leads to some surprisingly good results, and this paper brings these results together, as well as providing an introduction to some of the probabilistic methods needed. For the entire collection see [Zbl 0910.00036].
0 references
