Mathematical Induction and Graph Coloring

International Journal of Mathematical Trends and Technology (IJMTT)          
© 2011 by IJMTT Journal
Volume-2 Issue-2                           
Year of Publication : 2011
Authors : A.A.I Perera, D.G.T.K. Samarasiri


A.A.I Perera, D.G.T.K. Samarasiri"Mathematical Induction and Graph Coloring"International Journal of Mathematical Trends and Technology (IJMTT),V2(2):20-25.June 2011. Published by Seventh Sense Research Group.

Graph coloring can be used to solve problems in all disciplines. In our work, we have used Mathematical Induction to solve graph coloring problems. In this work, we proved that, a map which is formed by some finite number of line segments joining pairs of points on different sides of a given rectangle is 2-colorable.


[1]. K.H, Rosen Discrete Mathematics and its pplications, American Telephone and Telegraphic Company, USA, 1991.
[2]. J. W Robin., Introduction to Graph Theory, fourth edition, Longman group Ltd, 81-96, 1996.
[3]. F. Harary Graph Theory, Narosa publishing House, Calcutta, 1997.
[4]. D. Marx, Graph coloring problems and their applications in scheduling, Periodica Polytechnica, Proc. John von Neumann PhD Students Conference, pp. 1–2, 2004.
[5]. V. Guruswami,. S. Khanna, On the hardness of 4- coloring a 3-colorable graph, Proceedings of the 15th annual IEEE Conference on Computational Complexity, pp. 188–197, 2000.
[6]. D.W Matula, G. Marble and I.D. Isaacson Graph Coloring Algorithms in Graph Theory and Computing. R.C. Read (Ed) Academic Press, New York, 1972.

                 Cocycle matrix, bilinear forms.