Skip to Main content Skip to Navigation
Journal articles

Acyclic, Star and Oriented Colourings of Graph Subdivisions

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [46 references]  Display  Hide  Download

https://hal.inria.fr/hal-00959027
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 5:07:27 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:16:07 PM

File

dm070104.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00959027, version 1

Collections

Citation

David R. Wood. Acyclic, Star and Oriented Colourings of Graph Subdivisions. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2005, 7, pp.37-50. ⟨hal-00959027⟩

Share

Metrics

Record views

192

Files downloads

924