图的k-星着色的Grbner基求解

对于具有n个顶点的简单连通图G,首先证明求解G的k-星着色等价于一个多元多项式方程组在{1,2,…,k}上的求解问题,其次使用Grbner基给出求解该多元多项式方程组的方法,从而得到求G的星色数的一个可行途径,最后通过实例验证了此代数计算方法的有效性.

Solving the k- Star Coloring Problem of Graph by Gr~ibner Bases

In the report, let G be a simple connected graph of n vertices, that solving star chromatic number of G is equivalent to finding all{ 1,2,-- ,kl solutions of a system of multivariate polynomial equations; Grsbner ba- ses were used to propose the solving method of the multivariate polynomial equations, that a feasible way of find- ing star chromatic number of G was obtained; the numerical example was presented to illustrate the effectiveness of the algebraic computational method.