%0 Journal Article
%T Acyclic, Star and Oriented Colourings of Graph Subdivisions
%A David R. Wood
%J Discrete Mathematics & Theoretical Computer Science
%D 2005
%I Discrete Mathematics & Theoretical Computer Science
%X Let G be a graph with chromatic number ¦Ö(G). A vertex colouring of G is acyclic if each bichromatic subgraph is a forest. A star colouring of G is an acyclic colouring in which each bichromatic subgraph is a star forest. Let ¦Ö a (G) and ¦Ö s (G) denote the acyclic and star chromatic numbers of G. This paper investigates acyclic and star colourings of subdivisions. Let G' be the graph obtained from G by subdividing each edge once. We prove that acyclic (respectively, star) colourings of G' correspond to vertex partitions of G in which each subgraph has small arboricity (chromatic index). It follows that ¦Ö a (G'), ¦Ö s (G') and ¦Ö(G) are tied, in the sense that each is bounded by a function of the other. Moreover the binding functions that we establish are all tight. The oriented chromatic number ¦Ö ¡ú (G) of an (undirected) graph G is the maximum, taken over all orientations D of G, of the minimum number of colours in a vertex colouring of D such that between any two colour classes, all edges have the same direction. We prove that ¦Ö ¡ú (G')=¦Ö(G) whenever ¦Ö(G)¡Ý9.
%U http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/60