On Chromatic Number and Edge-Chromatic Number of the Ottomar Graph

Authors

  • Mark Caay Convergys Philippines, Apas, Cebu City, 6000 , Philippines
  • Esperanza Arugay Department of Mathematics, College of Science and Mathematics, Mindanao State University – Iligan Institute of Technology, Tibanga, Iligan City, 9200, Philippines

Keywords:

path, cycle, chromatic number, edge-chromatic number, ottomar graph, generalized ottomar graph.

Abstract

The path graph , consists of the vertex set  and the edge set .  The cycle graph , is the path graph,  with an additional edge    Define the Ottomar Graph, denoted by , to be the graph , with a vertex connected by a path  to a vertex of .   is called the heart while  is called a foot (feet for plural).   Note that there are  copies of .  The chromatic number of a graph , denoted by , is the minimum number of colors the vertices of  maybe colored such that any two adjacent vertices have different colors.  The edge-chromatic number of a graph , denoted by , is the minimum number of colors the edges of  maybe colored such that any two incident edges have different colors.  The chromatic number and the edge-chromatic number of the ottomar graph are determined.  When will the two invariants be equal or when will they be unequal?  When the connecting path  has order greater than 2, what happens to the value of  and ?  Also in the paper, the other coloring invariants are compared and investigated with chromatic number and edge-chromatic number.

References

[1]. E. Arugay. “Path Chromatic Number of a Graph.” In Dissertation Conference. Ateneo de Manila University, 1990.
[2]. R. Balakrishnan and K. Ranganathan. A Textbook of Graph Theory, 2nd Ed., Springer, 2012.
[3]. T. Harju. Lecture Notes on GRAPH THEORY. Department of Mathematics, University of Turku, FIN-20014, Turku, Finland, 2012.

Downloads

Published

2016-02-07

How to Cite

Caay, M., & Arugay, E. (2016). On Chromatic Number and Edge-Chromatic Number of the Ottomar Graph. American Scientific Research Journal for Engineering, Technology, and Sciences, 16(1), 98–107. Retrieved from https://asrjetsjournal.org/index.php/American_Scientific_Journal/article/view/1255

Issue

Section

Articles