The Penrose polynomial of a plane graph (Q1359525)

Some 25 years ago Penrose derived several remarkable expressions for the number of 3-edge colorings of a connected 3-regular plane graph \(G\), defining implicitly what is now called the Penrose polynomial \(P(G,\lambda)\). In this paper the Penrose polynomial is studied for arbitrary connected plane graphs. We give an equivalent definition of \(P(G,\lambda)\) in terms of cycles and cocycles and deduce some results on the coefficients and the evaluation of \(P(G,\lambda)\) at integral \(\lambda\). In particular, the Penrose formulae are generalized to arbitrary plane graphs. In addition, connections to the Tutte polynomial, transition systems and the 4-color theorem are discussed.