Application Of Graph Coloring Problem

The coloring is an important area of graph theory researches, which is also a new discipline rise at a rapid speed and it is widely used in recent years. The research methods of the graph coloring and its important theories have a very important position on the research of discrete mathematics, and it is also a core of the promotion of research and development on discrete mathematics and graph theory, which has an important theoretical value. At the same time, the continuing results of the study on coloring affect our real life in a large extent, such as the graph coloring can help us solve problems of the frequency allocation on communication systems, chemical storage, task scheduling, class arrangements, and school exam arrangements and other issues, which has a great practical and social significance.This article summarizes some basic theories of graph coloring, and introduces the concept, classification, the vertex coloring, the edge coloring and total coloring issues of graph, and makes a discussion and a research on greedy coloring algorithm, Welsh-powell coloring algorithm, vertex coloring algorithm based on the set theory, traditional direct heuristic algorithm, vertex coloring algorithm on the use of maximal independent set, edge coloring algorithm based on bipartite graph, undirected graph coloring algorithm based on vertex coloring, and makes an analysis on the advantages and disadvantages of these algorithms. The use of graph coloring algorithm gives an application model of school class and exam arrangement, which can help solve the time conflict problems among teachers, classes, students and classrooms in the class arrangements and examinations arrangements, which can improve the work efficiency. The use of vertex coloring algorithm can presents an application model for crops cultivation technology, which can solve the allelopathy problem among crops, and enhances the viability and efficiency of crops.