Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Notes on Nonrepetitive Graph Colouring. | Notes on Nonrepetitive Graph Colouring János Barat Department of Mathematics University of Szeged Szeged Hungary barat@ David R. Wood Department of Mathematics and Statistics The University of Melbourne Melbourne Australia Submitted Jul 18 2007 Accepted Jul 23 2008 Published Jul 28 2008 Mathematics Subject Classification 05C15 coloring of graphs and hypergraphs Abstract A vertex colouring of a graph is nonrepetitive on paths if there is no path v1 v2 . v2t such that Vi and Vt i receive the same colour for all i 1 2 . t. We determine the maximum density of a graph that admits a k-colouring that is nonrepetitive on paths. We prove that every graph has a subdivision that admits a 4-colouring that is nonrepetitive on paths. The best previous bound was 5. We also study colourings that are nonrepetitive on walks and provide a conjecture that would imply that every graph with maximum degree A has a f A -colouring that is nonrepetitive on walks. We prove that every graph with treewidth k and maximum degree A has a O kA -colouring that is nonrepetitive on paths and a O kA3 -colouring that is nonrepetitive on walks. 1 Introduction We consider simple finite undirected graphs G with vertex set V G edge set E G and maximum degree A G . Let t 1 2 . tg. A walk in G is a sequence v1 v2 . vt of vertices of G such that vivi 1 2 E G for all i 2 t 1 . A k-colouring of G is a function f that assigns one of k colours to each vertex of G. A walk v1 v2 . v2t is repetitively coloured by f if f vi f vt i for all i 2 t . A walk v1 v2 . v2t is boring if vi vt i for all i 2 t . Of course a boring walk is repetitively coloured by every colouring. We say a colouring f is nonrepetitive on walks or walk-nonrepetitive if the only walks that Research supported by a Marie Curie Fellowship of the European Community under contract number HPMF-CT-2002-01868 and by the OTKA Grant . yResearch supported by a QEII Research Fellowship. Research conducted at the
