Mathematical Induction and Graph Coloring

A.A.I Perera; D.G.T.K. Samarasiri

doi:https://doi.org/10.14445/22315373/IJMTT-V2I2P505

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 2 | Issue 2 | Year 2011 | Article Id. IJMTT-V2I2P505 | DOI : https://doi.org/10.14445/22315373/IJMTT-V2I2P505

Mathematical Induction and Graph Coloring

A.A.I Perera, D.G.T.K. Samarasiri

Abstract

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.

Keywords

Cocycle matrix, bilinear forms.

References

[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.

Citation :

A.A.I Perera, D.G.T.K. Samarasiri, "Mathematical Induction and Graph Coloring," International Journal of Mathematics Trends and Technology (IJMTT), vol. 2, no. 2, pp. 18-25, 2011. Crossref, https://doi.org/10.14445/22315373/IJMTT-V2I2P505