Skip to Main content Skip to Navigation
Journal articles

On the Oriented Chromatic Index of Oriented Graphs

Pascal Ochem 1 Alexandre Pinlou 2, * Eric Sopena 3
* Corresponding author
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A homomorphism from an oriented graph G to an oriented graph H is a mapping f from the set of vertices of G to the set of vertices of H such that f(U)f(V) is an arc in H whenever 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. 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00195956
Contributor : Alexandre Pinlou <>
Submitted on : Friday, September 18, 2020 - 11:23:46 AM
Last modification on : Thursday, July 8, 2021 - 3:48:15 AM
Long-term archiving on: : Friday, December 4, 2020 - 5:53:36 PM

File

ark__67375_WNG-M74PPFVQ-B.pdf
Publication funded by an institution

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Pascal Ochem, Alexandre Pinlou, Eric Sopena. On the Oriented Chromatic Index of Oriented Graphs. Journal of Graph Theory, Wiley, 2008, 57 (4), pp.313-332. ⟨10.1002/jgt.20286⟩. ⟨lirmm-00195956⟩

Share

Metrics

Record views

298

Files downloads

60