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?



How to translate a graph coloring problem to algebraic or geometric language and solve it?
See Sebastian A. Csar, Rik Sengupta, and Warut Suksompong, [On a subposet of the Tamari lattice](https://arxiv.org/pdf/1108.5690.pdf); 


"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. 


