Open Access
Subscription or Fee Access
Vertex Coloring of a Graph
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:
PDFReferences
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.
This work is licensed under a Creative Commons Attribution 3.0 License.