Carleton University
Technical Report TR-03-02
March 2003
Star Colourings of Subdivisions
Abstract
et G be a graph with chromatic number χ ( G ) and maximum degree ∆( G ) . A star colouring of G is a function that assigns a colour to each vertex such that adja- cent vertices receive distinct colours, and there is no bichromatic 4-vertex path. The star chromatic number χ st ( G ) is the minimum number of colours in a star colour- ing of G . Star colourings of subdivisions of graphs are investigated. Let G 0 be the graph obtained from G by subdividing each edge once. Bounds on χ st ( G 0 ) in terms of χ ( G ) and ∆( G ) are proved. In particular, χ st ( G 0 ) ≤ max { χ ( G ) , 3 } and χ st ( G 0 ) ≤ p ∆( G )+3 . Furthermore, if χ st ( G 0 ) ≤ k then χ ( G ) ≤ k · 2 2 k . Hence χ st ( G 0 ) is tied to χ ( G ) . On the other hand, a graph H obtained from G by subdivid- ing each edge at least twice has χ st ( H ) ≤ 4