Premium
On the oriented chromatic index of oriented graphs
Author(s) -
Ochem Pascal,
Pinlou Alexandre,
Sopena Éric
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20286
Subject(s) - combinatorics , mathematics , homomorphism , digraph , chromatic polynomial , graph homomorphism , bounded function , discrete mathematics , graph , chromatic scale , critical graph , graph power , line graph , mathematical analysis
A homomorphism from an oriented graph G to an oriented graph H is a mapping $\varphi$ from the set of vertices of G to the set of vertices of H such that $\buildrel {\longrightarrow}\over {\varphi (u) \varphi (v)}$ is an arc in H whenever $\buildrel {\longrightarrow}\over {uv}$ is an arc in G . The oriented chromatic index of an oriented graph G is the minimum number of vertices in an oriented graph H such that there exists a homomorphism from the line digraph LD( G ) of G to H (the line digraph LD(G) of G is given by V (LD( G )) = A( G ) and $\buildrel {\longrightarrow}\over {ab} \in A(LD(G))$ whenever $a=\buildrel {\longrightarrow}\over {uv}$ and $a=\buildrel {\longrightarrow}\over {vw}$ ). We give upper bounds for the oriented chromatic index of graphs with bounded acyclic chromatic number, of planar graphs and of graphs with bounded degree. We also consider lower and upper bounds of oriented chromatic number in terms of oriented chromatic index. We finally prove that the problem of deciding whether an oriented graph has oriented chromatic index at most k is polynomial time solvable if k ≤ 3 and is NP‐complete if k ≥ 4. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 313–332, 2008