Uniquely colourable m-dichromatic oriented graphs
type: Item
instance of: scholarly article
title: Uniquely colourable m-dichromatic oriented graphs
zbMATH Open document ID: 0613.05023
DOI: 10.1016/0012-365X(86)90042-7
author: N. Santoro
author: V. Neumann-Lara
author: J. Urrutia
published in: Discrete Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The dichromatic number \(d_ k(D)\) of a digraph D is the minimum number of colours needed to colour V(D) in such a way that no monochromatic directed cycle is obtained. A digraph D is called uniquely colourable if any acyclic \(d_ k(D)\)-colouring of V(D) induces the same partition of V(D). The authors construct an infinite family of uniquely colourable m- dichromatic oriented graphs for all \(m\geq 2\). They give first of all two families of uniquely colourable 2-dichromatic oriented graphs \(\{H_ r- 0\}^{\infty}_{r=4}\), \(\{H_ r-(r,0)\}^{\infty}_{r=4}\). In both cases \(H_ r\) denotes a graph with vertex set \(I=\{0,1,2,...,2r\}\) the arcs of which are ordered pairs (i,j), i,j\(\in I\), where \(j=i+1\), \(i+2,...,i+r-1\), \(i+r+1 (mod 2r)\). For \(m>2\) the authors construct the uniquely colourable m-dichromatic oriented graphs by induction over m.
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3991529
zbMATH Keywords: acyclic m-colouring
zbMATH Keywords: uniquely m-colourable graph
zbMATH Keywords: dichromatic number
MaRDI profile type: Publication
cites work: Q3882513
cites work: On the decomposition of a minimally strongly h-connected digraph into h+1 acircuitic subgraphs
cites work: The dichromatic number of a digraph
cites work: Q3693540
cites work: Vertex critical r-dichromatic tournaments
full work available at URL: 0012-365x(86)90042-7
OpenAlex ID: W2022024983
description: scientific article; zbMATH DE number 3991529