A graph G with n vertices and maximum degree ΔG cannot be given weak sense of direction using less than ΔG colours. It is known that n colours are always sufficient, and it was conjectured that just ΔG+1 are really needed, that is, one more colour is sufficient. Nonetheless, it has just been shown that for sufficiently large n there are graphs requiring ω(n/log n) more colours than ΔG. In this paper, using recent results in asymptotic graph enumeration, we show not only that (somehow surprisingly) the same bound holds for regular graphs, but also that it can be improved to Ω(n log log n/log n) We also show that Ω(dG(log log dG)1/2 colours are necessary, where dG is the degree of G.
Lower bounds for sense of direction in regular graphs / P. Boldi, S. Vigna. - In: DISTRIBUTED COMPUTING. - ISSN 0178-2770. - 16:4(2003), pp. 279-286.
Lower bounds for sense of direction in regular graphs
P. BoldiPrimo
;S. VignaUltimo
2003
Abstract
A graph G with n vertices and maximum degree ΔG cannot be given weak sense of direction using less than ΔG colours. It is known that n colours are always sufficient, and it was conjectured that just ΔG+1 are really needed, that is, one more colour is sufficient. Nonetheless, it has just been shown that for sufficiently large n there are graphs requiring ω(n/log n) more colours than ΔG. In this paper, using recent results in asymptotic graph enumeration, we show not only that (somehow surprisingly) the same bound holds for regular graphs, but also that it can be improved to Ω(n log log n/log n) We also show that Ω(dG(log log dG)1/2 colours are necessary, where dG is the degree of G.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.