Lower bounds for weak sense of direction
Sebastiano Vigna, Paolo Boldi · INFM-OAR (INFN Catania) · 2003
A graph with n vertices and maximum degree Δ cannot be given weak sense of direction using less than Δ colours. It is known that n colours are always sufficient, but it has been conjectured that just Δ + 1 are really needed. On the contrary, we show that for sufficiently large n there are graphs requiring Δ + ω((n log log n)/log n) colours. Moreover, we prove that, in terms of the maximum degree, Ω(Δ√log log Δ) colours are necessary.