Math 2.0

Combinatorics Concept

Greedy colouring

Summary

Greedy colouring is a simple method that makes a colouring of a finite graph. Put the vertices in an order v1,v2,…,vnv_1, v_2, \dots, v_n, and use the colours 1,2,3,…1, 2, 3, \dots. For i=1,…,ni = 1, \dots, n, give viv_i the smallest colour that no earlier neighbour of viv_i has.

Remarks

A vertex viv_i has at most deg⁡(vi)\deg(v_i) earlier neighbours. Thus greedy colouring uses at most Δ(G)+1\Delta(G) + 1 colours, where Δ(G)\Delta(G) is the maximum degree. The number of colours depends on the order. For each graph, some order gives an optimal colouring, but such an order is hard to find in general. Greedy colouring can be done in linear time.

Further reading

  1. Web https://en.wikipedia.org/wiki/Greedy_coloring, Algorithm
About this page
Tag04AAKZNXHD
URIm2://04AAKZNXHD
Kindconcept
WritingW0 stub
MSC05C15
SpecializesGraph colouring
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.