David R. Wood - Acyclic, Star and Oriented Colourings of Graph Subdivisions

dmtcs:344 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, Vol. 7 - https://doi.org/10.46298/dmtcs.344
Acyclic, Star and Oriented Colourings of Graph SubdivisionsArticle

Authors: David R. Wood ORCID1

  • 1 Departament de Matemàtica Aplicada II

Let G be a graph with chromatic number χ (G). A vertex colouring of G is \emphacyclic if each bichromatic subgraph is a forest. A \emphstar 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 \emphoriented 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.


Volume: Vol. 7
Published on: January 1, 2005
Imported on: March 26, 2015
Keywords: subdivision,oriented chromatic number,oriented colouring,graph,graph colouring,star colouring,star chromatic number,acyclic colouring,acyclic chromatic number,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

23 Documents citing this article

Consultation statistics

This page has been seen 341 times.
This article's PDF has been downloaded 353 times.