_"[The number of edge 3-colorings of a planar cubic graph as a permanent](https://www.sciencedirect.com/science/article/pii/0012365X74901575)"_ 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](https://www.researchgate.net/publication/220342879_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 <a href="http://www.math.brown.edu/~rkenyon/talks/CRSFs.pdf">talk</a> that Kenyon gave this year at the JMM. This new approach generalizes Kirkhoff's theorem from spanning trees to cycle-rooted-spanning-forests