Open Access Open Access  Restricted Access Subscription or Fee Access

Vertex Coloring of a Graph

P. Ramya, A. Gracy

Abstract


Graph coloring is one of the most important concepts in graph theory and is used in many real time applications. Various coloring methods are available and can be used on requirement basis. The proper coloring of a graph is the coloring of the vertices and edges with minimal number of colors such that no two vertices should have the same color. The minimum number of colors is called as the chromatic number and the graph is called properly colored graph. In this paper we reviewed the vertex coloring concepts, properties and theorem related to various graphs of vertex colorings and its chromatic number.

Keywords


Vertex Coloring, Minimum Degree, Maximum Degree, Chromatic Number.

Full Text:

PDF

References


Wilson, R.J., 1996. Introduction to Graph Theory, (Pearson Education Ltd.).

Christofides, N. "An Algorithm for the Chromatic Number of a Graph." Computer J 14, 38-39, 1971. Gould, R. (Ed.). Graph Theory. Menlo Park, CA: Benjamin-Cummings, 1988.

Bondy, J.A. and Murty, U.S.R., 1985. Graph Theory with Applications, (Elsevier Science Publishing Co., Inc.).

Balakrishnan, R. and Ranganathan, K., 2000. A Textbook of Graph Theory, Springer-Verlag).

Thulasiraman, K. and Swamy, M.N.S., 1992. Graphs: Theory and Algorithms, (JohnWiley & Sons, Inc.).


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.