"The number of edge 3-colorings of a planar cubic graph as a permanent" by David E. Scheim gives a permanent formula for the number of edge-3-colorings of planar cubic graphs (i.e. the number of 3-coloring of graphs which are line graphs of cubic planar graphs.)
This is generalized (using some results of Ellingham and Goddyn) to the case of n-colorings of n-regular planar graphs in "Colorings and orientations of matrices and graphs" by Uwe Schauz. This paper interprets Ryser's permanent formula as a statement about colorings and gives a "matrix form" of a theorem of Alon and Tarsi.
This doesn't answer your question but I hope you find the above references interesting. On the other hand about the fact that the Laplacian matrix generalizes to the Laplace operator on graphs, I wanted to mention that, in turn, it generalizes to the Laplacian on vector bundles on graphs. I learned about this generalization in the talk that Kenyon gave this year at the JMM. This new approach generalizes Kirkhoff's theorem from spanning trees to cycle-rooted-spanning-forests
