How to translate a graph coloring problem to algebraic or geometric language and solve it? I want to know whether there are ways to use algebraic methods for solving graph theory  problems (graph coloring problems). For example, is it possible to prove the four-color theorem purely with algebraic or geometric methods?
 A: See Sebastian A. Csar, Rik Sengupta, and Warut Suksompong, On a subposet of the Tamari lattice; 
"Relying on work of Whitney in [13], Kauffman reformulated the Four Color Theorem using the vector cross product in [5]. More recently, in [ 1], Cooper, Rowland and Zeilberger transformed the Four Color Theorem into a question about another binary function on $T_n$: the size of the set ParseWords$(T_1, T_2)$ consisting of all words $w \in \{\,0, 1, 2\,\}^n$ which are parsed by both $T_1$ and $T_2$. Here, a word $w$ is parsed by $T$ if the labeling of the leaves of $T$ by $w_1,w_2,\dots,w_n$ from left to right extends to a proper 3-coloring with colors $\{\,0, 1, 2\,\}$ of all $2n − 1$ vertices in $T$ , such that no two children of the same vertex have the same label and such that no parent and child share the same label. The Four Color Theorem is equivalent to the statement that for all $n$ and all $T_1,T_2 \in T_n$, one has $|{\rm ParseWords}(T_1 , T_2 )| \ge 1$. Tamari offers a similar reformulation of the Four Color Theorem in [12]."
Perhaps this will go some way to answering Gordon Royle's question in the comments. The Kauffman reference is to Kauffman, Louis H., Map coloring and the vector cross product, J. Combin. Theory Ser. B 48 (1990), no. 2, 145–154, MR1046751 (91b:05078). Here is an excerpt from the review by François Jaeger: 
This paper presents a nice algebraic reformulation of the four color theorem. Consider an orthonormal basis $i,j,k$ of ${\bf R}^3$ endowed with the usual vector cross product written multiplicatively (so that $ij=k=−ji$, $i^2=0$, and so on). Let $L$ and $R$ be two expressions formed from a word $X_1\cdots X_n$ by correct insertion of parentheses (i.e. $L$ and $R$ represent well-defined products). A sharp solution of the equation $L=R$ is an assignment of values $i,j,k$ to each variable $X_r$ such that the resulting values for $L$ and $R$ (using the vector cross product) are equal and nonzero. For instance a sharp solution to the equation $X_1(X_2X_3)=(X_1X_2)X_3$ is given by $X_1=i$, $X_2=k$, $X_3=i$. Then the four color theorem is equivalent to the statement that every equation of the form $L=R$ has a sharp solution.
Another paper worth a mention is Miranda, Rick, Colorings of planar maps and residues of 1-forms, Methods in module theory (Colorado Springs, CO, 1991), 237–247, Lecture Notes in Pure and Appl. Math., 140, Dekker, New York, 1993, MR1203811 (94b:05086). The review by Steve Fisk says, 
This paper interprets coloring in terms of algebraic geometry. A cubic map on the sphere corresponds to a set of lines in a projective space, considered as a variety. A coloring with $q$ colors corresponds to a 1-form over ${\bf F}_q$ with all nonzero residues. 
Fisk also writes, 
There are many reformulations of coloring and the four-color problem [see T. L. Saaty, Amer. Math. Monthly 79 (1972), 2–43; MR0295965; B. T. Datta, in Graph theory and related topics (Waterloo, ON, 1977), 121–131, Academic Press, New York, 1979; MR0538040; F. Jaeger, J. Combin. Theory Ser. B 26 (1979), no. 2, 205–216; MR0532588; D. W. Barnette, Map coloring, polyhedra, and the four-color problem, Math. Assoc. America, Washington, DC, 1983....
so perhaps it would be worthwhile tracking down those references. 
Continuing to follow my nose through the internet, I come across Matiyasevich, Yuri, Some arithmetical restatements of the four color conjecture, Weak arithmetics. Theoret. Comput. Sci. 257 (2001), no. 1-2, 167–183, MR1825093 (2002f:03107), where the summary reads, in part, 
The four colour conjecture is reformulated as a statement about non-divisibility of certain binomial coefficients. 
A: Bruce Richmond and David Jackson (both old-timers in combinatorial asymptotics) recently put a computer-free proof on the arXiv.
I'll summarize the method.
(1) If any planar map is not 4-colourable, then almost all planar maps are not 4-colourable. (Here, "almost all" means that the fraction tends to 1 as the size tends to infinity.) This follows from a previous result that any fixed planar map is a submap of almost all planar maps, so a non-4-colourable planar map will be present in most planar maps thus blocking their 4-colourability.
(2) (This is the breakthrough part.) The paper now constructs a family of 4-colourable planar maps that form a positive fraction of all planar maps.
The combination of (1) and (2) proves that all planar maps are 4-colourable. Not a computer in sight.
SADLY, this claim has been withdrawn due to an error in the proof.
