On the number of 3-edge colorings of cubic graphs (Q1348773): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q190560 |
||
Property / reviewed by | |||
Property / reviewed by: Ioan Tomescu / rank | |||
Revision as of 12:05, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the number of 3-edge colorings of cubic graphs |
scientific article |
Statements
On the number of 3-edge colorings of cubic graphs (English)
0 references
23 September 2002
0 references
The Penrose polynomial of a plane cubic graph was introduced by \textit{R. Penrose} [Comb. Math. Appl., Proc. Conf. Math. Inst., Oxford 1969, 221-224 (1971; Zbl 0216.43502)]. In this paper the Penrose polynomial is introduced for binary matroids and it is expressed as a sum of characteristics polynomials of some associated binary matroids. It is presented a short algebraic proof for a generalization of a formula of Penrose on the number of 3-edge colorings of a plane cubic graph and it is shown that the number of 3-edge colorings of cubic graphs can be computed (up to a factor of \(2^{|E|/3-1}\)) by evaluating the Penrose polynomial of their cycle space at 4.
0 references
Penrose polynomial
0 references
plane cubic graph
0 references
3-edge coloring
0 references
binary matroid
0 references
matroids
0 references