论文标题
非反复图形着色
Nonrepetitive graph colouring
论文作者
论文摘要
如果$ g $不包含该路径的前半部分的颜色序列与下半部分配相同的颜色序列，则图$ g $的顶点着色是“非重复”。 Thue的著名定理说，每条道路都不可预三色。本文调查了图形的非重复着色的结果。目的是对主要结果和证明方法进行统一，全面的介绍，并突出许多开放问题。
A vertex colouring of a graph $G$ is "nonrepetitive" if $G$ contains no path for which the first half of the path is assigned the same sequence of colours as the second half. Thue's famous theorem says that every path is nonrepetitively 3-colourable. This paper surveys results about nonrepetitive colourings of graphs. The goal is to give a unified and comprehensive presentation of the major results and proof methods, as well as to highlight numerous open problems.
