Homomorphisms and colourings of oriented graphs: An updated survey

An oriented graph is a loopless digraph with no opposite arcs. An oriented k-colouring of an oriented graph G⃗ is a partition of its set of vertices into k parts in such a way that no two adjacent vertices belong to the same part, and all the arcs connecting every two parts have the same direction....

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2016-07, Vol.339 (7), p.1993-2005
Main Author: Sopena, E
Format: Article
Language:English
Subjects:
Colouring
Computer Science
Discrete Mathematics
Equivalence
Graph theory
Graphs
Homomorphism
Homomorphisms
Joining
Mathematical analysis
Oriented chromatic number
Oriented colouring
Oriented graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An oriented graph is a loopless digraph with no opposite arcs. An oriented k-colouring of an oriented graph G⃗ is a partition of its set of vertices into k parts in such a way that no two adjacent vertices belong to the same part, and all the arcs connecting every two parts have the same direction. Hence, such a colouring exists if and only if G⃗ admits a homomorphism to some oriented graph of order k. The oriented chromatic number of G⃗ is then defined as the smallest k for which G⃗ admits an oriented k-colouring or, equivalently, as the minimum order of an oriented graph to which G⃗ admits a homomorphism. In this paper, we survey the main results about oriented colourings and propose a few open problems.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2015.03.018