The Polynomial Modeling And Grobner Basis Solving Of Several Problems In Graph Theory

This thesis is devoted to an algebraic study of the following problems in graph theory:1. The problem of independent set;2. The problem of covering;3. The problem of matching and perfect matching;4. The problem of backbone coloring;5. The problem of total coloring;6. The problem of strong coloring;7. The problem of (k,d)-coloring. Comparing to the already existed study of the same problems in the literature, where most of the results are either seeking the maximal or minimal solutions by means of a certain optimization method or restricted to some special types of graphs, we solve the listed problems by introducing, for an arbitrary finite graph G and a positive integer k, the k-counting problem with respect to the problems in1-7respectively, that is, the problem of k-independent set; the problem of k-covering; the problem of k-matching; the problem of k-backbone coloring; the problem of k-total coloring; the problem of k-strong coloring; and the problem of (k, d)-coloring. The main results we obtained are:●A mathematical model for each k-counting problem is given by a system of polynomial equations;●An effective criterion for checking the existence of solutions to the k-counting models is given in terms of Grobner basis method;●In the case that a k-counting model has a solution, the Grobner basis method for finding all solutions is given;●A maximal or minimal solution, or an invariant (e.g. chromatic number) asked by a k-counting model may be found among the solutions obtained in the last step.Since the polynomial models we constructed are independent of the types and size of the given graphs, and since nowadays Grobner basis method has been a well-developed, powerful and efficient method in solving system of polynomial equations on computer, the results obtained in this thesis are not only effective in solving the foregoing problems for each arbitrarily given graph, helpful in examining some important conjectures (for instance, the total coloring conjecture), but also provides a feasible theoretical foundation for the polynomial modeling and Grobner basis solving of certain similar discrete mathematical problems.