On the number of 3-edge colorings of cubic graphs
type: Item
instance of: scholarly article
title: On the number of 3-edge colorings of cubic graphs
zbMATH Open document ID: 0993.05069
author: Christian Szegedy
published in: European Journal of Combinatorics
publication date: 2002-09-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 1740673
zbMATH Keywords: Penrose polynomial
zbMATH Keywords: plane cubic graph
zbMATH Keywords: 3-edge coloring
zbMATH Keywords: binary matroid
zbMATH Keywords: matroids
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
OpenAlex ID: W1978463456
cites work: The Penrose polynomial of a plane graph
cites work: A new 5‐arc‐transitive cubic graph
cites work: Q4012032
cites work: On Tutte polynomials and cycles of plane graphs
cites work: On the Penrose number of cubic diagrams
cites work: Q3822184
cites work: On Tutte polynomials of matroids representable over \(GF(q)\)
cites work: On the Principal Edge Tripartition of a Graph
cites work: Q4111952
cites work: Q3140234
DOI: 10.1006/EUJC.1999.0440
description: scientific article; zbMATH DE number 1740673