Research And Application Of Several Classes Of Graph Coloring Problems Via The Semi-tensor Product Method

The graph coloring problem, a classical problem of graph theory, was shown a very difficult and NP-hard problem in the earlier 70’s of the last century. It has not only played an important role in the development of graph theory, but also found a wide range of applications in real life such as air traffic flow management, timetabling, scheduling, and frequency assignment. So, this research has very im-portant theoretical and practical significance. Due to the diversity of graph coloring problem, study on coloring problem is based on specific forms of the coloring prob-lem as the research object. In this paper, the robust graph coloring, the T-coloring, list coloring and Conflict-free coloring of hypergraph as well as fuzzy graph coloring problem, are studied by using the semi-tensor product, and a number of new algebra results and algorithms are presented. In addition, the obtained results are applied to the examination timetabling problem and frequency assignment problem in wireless communication. The main contents of this paper are listed as follows:1. The robust graph coloring problem with application to a kind of examina-tion timetabling problem is studied, and a number of new results and algorithms are presented. Using the semi-tensor product, the robust graph coloring problem is expressed into a kind of optimization problem taking in an algebraic form of matri-ces, and an algorithm is designed to find all the most robust coloring schemes for any simple graph. Furthermore, an equivalent problem of the robust graph color-ing is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. In addi-tion, as an application, a kind of examination timetabling is discussed by employing aforementioned results, and a method to design a practicable timetabling scheme is achieved. The study of two illustrative examples has shown the effectiveness of our results/algorithms.2. The T-coloring and the list coloring of simple graphs with application to fre- quency assignment are investigated by using the matrix semi-tensor product. Firstly, using the matrix semi-tensor product, the T-coloring problem is studied, and two nec-essary and sufficient conditions are put forward for T-colorability, based on which a new algorithm is established to find all the T-coloring schemes for any simple graph. Secondly, the list coloring problem is considered, and one necessary and suf-ficient condition is obtained for the list coloring, based on which one necessary and sufficient condition is derived for the list T-coloring. Thirdly, a kind of frequen-cy assignment problem is discussed by using the obtained results, and a method to design a feasible assignment scheme is presented. Finally, the effectiveness of the results/algorithms is substantiated by two illustrative examples.3. Using the matrix semi-tensor product, the Conflict-free coloring problem of hypergraphs is investigated, and several new results and algorithms are proposed. By incidence matrix and characteristic logical vector, two necessary and sufficient conditions are proposed for the Conflict-free coloring problem, based on which a new algorithm is established to find all the Conflict-free coloring schemes for any hypergraph. Then the obtained results are applied to frequency assignment problem to show the effectiveness and applicability of the results and algorithms.4. Using the semi-tensor product of matrices, the stable set and vertex coloring problems of fuzzy graphs are considered, and several new results and algorithms are put forward. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for the fuzzy internally stable set problem, based on which a new algorithm to find all the stable sets is established for any fuzzy graph. Secondly, the coloring problem of fuzzy graph is studied by using the semi-tensor product method, and two necessary and sufficient conditions are proposed for the colorability, based on which a new algorithm to find all the fuzzy coloring schemes and the chromatic number is put forward. Finally, the study of illustrative examples to support our results/algorithms.