zbMATH — the first resource for mathematics

On Tutte polynomials and cycles of plane graphs. (English) Zbl 0595.05033
Let t(G,x,y) be the Tutte polynomial (or dichromate) of the connected plane graph G. It is known (Martin; Las Vergnas) that t(G,x,x) can be expressed in terms of the family of partitions of the edge-set of the medial graph M(G) of G into non-crossing cycles. Moreover, t(G,-1,-1) can be expressed in terms of the number of crossing cycles of M(G) (Martin; Rosenstiehl and Read).
Another result of Penrose on the number of edge-3-colorings of a cubic connected plane graph G can be viewed as an evaluation of t(G,0,-3) in terms of the family of partitions of the edge-set of M(G) into cycles avoiding certain transitions. We unify and generalize these results by giving expressions of t(G,x,y) in terms of cycle partitions of M(G) for all x, y such that (x-1)(y-1)\(\neq 0\) or \(x=y=1\).

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
Full Text: DOI
[1] Martin, P, Enumérations eulériennes dans LES multigraphes et invariants de Tutte-Grothendieck, Thesis, (1977), Grenoble
[2] Las Vergnas, M, Eulerian circuits of 4-valent graphs embedded in surfaces, () · Zbl 0472.05043
[3] Martin, P, Remarkable valuation of the dichromatic polynomial of planar multigraphs, J. combin. theory ser. B, 24, 318-324, (1978) · Zbl 0321.05108
[4] Rosenstiehl, P; Read, R.C, On the principal edge tripartition of a graph, Ann. discrete math., 3, 195-226, (1978) · Zbl 0392.05059
[5] Penrose, R, Applications of negative dimensional tensors, (), 221-244
[6] Berge, C, ()
[7] Bondy, J.A; Murty, U.S.R, ()
[8] Ore, O, ()
[9] Welsh, D.J.A, ()
[10] Tutte, W.T, A ring in graph theory, (), 26-40 · Zbl 0031.41803
[11] Tutte, W.T, A contribution to the theory of chromatic polynomials, Canad. J. math., 6, 80-91, (1954) · Zbl 0055.17101
[12] Kotzig, A, Eulerian lines in finite 4-valent graphs and their transformations, (), 219-230 · Zbl 0159.54201
[13] Rosenstiehl, P, Bicycles et diagonales des graphes planaires, Cahiers centre études rech. opér., 17, No. 2-4, 365-383, (1975) · Zbl 0328.05104
[14] Shank, H, The theory of left-right paths, (), 42-54, No. 452 · Zbl 0307.05120
[15] \scF. Jaeger, On edge-colorings of cubic graphs and a formula of Roger Penrose, in “Graph Theory in Memory of G. A. Dirac” (L. D. Andersen, Ed.), in press. · Zbl 0669.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.