The oriented chromatic number of edge-amalgamation of cycle graph

Dina Eka Nurvazly, Jona Martinus Manulang, Kiki A. Sugeng

Abstract


An oriented k − coloring of an oriented graph G⃗ is a partition of V(G⃗) into k color classes such that no two adjacent vertices belong to the same color class, and all the arcs linking the two color classes have the same direction. The oriented chromatic number of an oriented graph G⃗ is the minimum order of an oriented graph H⃗ to which G⃗ admits a homomorphism to H⃗. The oriented chromatic number of an undirected graph G is the maximum oriented chromatic number of all possible orientations of the graph G. In this paper, we show that every edge amalgamation of cycle graphs, which also known as a book graph, has oriented chromatic number less than or equal to six.


Keywords


edge amalgamation of cycle; homomorphism; oriented chromatic number

Full Text:

PDF

References


N. R. Aravind, N. Narayanan and C. R. Subramanian, Oriented colouring of some graph products, Discussiones Math. Graph Theory 31 (2011), 675--686.

A. V. Kostochka, E. Sopena and X. Zhu, Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, 24 (1997), 331--340.

E. Sopena, The chromatic number of oriented graphs, J. Graph Theory 25 (1997), 191--205.

E. Sopena, Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs, Discussiones Math. Graph Theory 32 (2012), 517--533.

E. Sopena, Homomorphisms and colourings of oriented graphs, Discrete Math. 339 (2016), 1993--2005.




DOI: http://dx.doi.org/10.19184/ijc.2019.3.1.5

Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats