Recognizing Graph Theoretic Properties with Polynomial Ideals

Details Recognizing Graph Theoretic Properties with Polynomial Ideals Recognizing Graph Theoretic Properties with Polynomial Ideals

2010-02-23

arxiv.org/abs/1002.4435v3

Mathematics

Combinatorics

20 pages, 3 figures

Scientific paper

Many hard combinatorial problems can be modeled by a system of polynomial equations. N. Alon coined the term polynomial method to describe the use of nonlinear polynomials when solving combinatorial problems. We continue the exploration of the polynomial method and show how the algorithmic theory of polynomial ideals can be used to detect k-colorability, unique Hamiltonicity, and automorphism rigidity of graphs. Our techniques are diverse and involve Nullstellensatz certificates, linear algebra over finite fields, Groebner bases, toric algebra, convex programming, and real algebraic geometry.

Affiliated with

Also associated with

No associations

Rating

Recognizing Graph Theoretic Properties with Polynomial Ideals does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Recognizing Graph Theoretic Properties with Polynomial Ideals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recognizing Graph Theoretic Properties with Polynomial Ideals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-260138