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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2005, 7, pp.37-50
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00959027
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 17:07:27
Dernière modification le : samedi 3 mars 2018 - 01:04:58
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:16:07

Fichier

dm070104.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

123

Téléchargements de fichiers

223