On the number of 3-edge colorings of cubic graphs (Q1348773): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:02, 5 March 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