Colorings and Orientations of Matrices and Graphs

Abstract

We introduce colorings and orientations of matrices as generalizations of the graph theoretic terms. The permanent per$(A[\zeta|\xi])$ of certain copies $A[\zeta|\xi]$ of a matrix $A$ can be expressed as a weighted sum over the orientations or the colorings of $A$. When applied to incidence matrices of graphs these equations include Alon and Tarsi's theorem about Eulerian orientations and the existence of list colorings. In the case of planar graphs we deduce Ellingham and Goddyn's partial solution of the list coloring conjecture and Scheim's equivalency between not vanishing permanents and the four color theorem. The general concept of matrix colorings in the background is also connected to hypergraph colorings and matrix choosability.