Acyclic colouring of graphs
Acyclic colouring of graphs
复制标题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
N. Alon;C. McDiarmid
中科院分区：
文献类型：
--
作者：
N. Alon;C. McDiarmid
图G的一个顶点着色称为无圈的，如果G中没有相邻两个顶点具有相同的颜色，并且G中不存在双色圈。图G的无圈色数记为A（G），是图G的无圈染色中的最少颜色数。证明了若G有最大度d，则当d → ∞时A（G）= O（d43）.这解决了Erdans在1976年提出的一个问题，即当d →∞时A（G）= o（d2）。我们还证明了存在最大度为d的图G，使得A（G）= Ω（d 4 3 /（log d）1 3）;并且证明了任何最大度为d的图的边都可以被O（d）种颜色着色，使得没有两个相邻的边具有相同的颜色，也不存在双色圈.所有的证明都很大程度上依赖于概率论证。
A vertex colouring of a graph G is called acyclic if no two adjacent vertices have the same colour and there is no two-coloured cycle in G. The acyclic chromatic number of G, denoted by A(G), is the least number of colours in an acyclic colouring of G. We show that if G has maximum degree d then A(G) = O(d 4 3 ) as d → ∞. This settles a problem of Erdős who conjectured, in 1976, that A(G) = o(d2) as d →∞. We also show that there are graphs G with maximum degree d for which A(G) = Ω(d 4 3 /(log d) 1 3 ); and that the edges of any graph with maximum degree d can be coloured by O(d) colours so that no two adjacent edges have the same colour and there is no two-coloured cycle. All the proofs rely heavily on probabilistic arguments.