Uniquely colourable m-dichromatic oriented graphs (Q1088673): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Víctor Neumann-Lara / rank | |||
Property / author | |||
Property / author: Jorge Urrutia / rank | |||
Property / author | |||
Property / author: Víctor Neumann-Lara / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Jorge Urrutia / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3882513 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the decomposition of a minimally strongly h-connected digraph into h+1 acircuitic subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The dichromatic number of a digraph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3693540 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Vertex critical r-dichromatic tournaments / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Uniquely colourable m-dichromatic oriented graphs / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(86)90042-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2022024983 / rank | |||
Normal rank |
Latest revision as of 10:51, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Uniquely colourable m-dichromatic oriented graphs |
scientific article |
Statements
Uniquely colourable m-dichromatic oriented graphs (English)
0 references
1986
0 references
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.
0 references
acyclic m-colouring
0 references
uniquely m-colourable graph
0 references
dichromatic number
0 references
0 references