✦ LIBER ✦

The number of edge 3-colorings of a planar cubic graph as a permanent

✍ Scribed by David E. Scheim

Publisher: Elsevier Science
Year: 1974
Tongue: English
Weight: 370 KB
Volume: 8
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(74)90157-5

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we establish that the number of edge 3-colorings of a finite planar cubic graph G, i.e., 3-colorings of its interchange graph H, is equal to 2*lPermanent(A)l, where N is the number of edges of G, and A is the 2N X 2iV square matrix formed by repeating each row of the N X 2N vertexdirected edge incidence matrix of H (with an arbitrary orientation). As the number of 4-colorings of a finite maximal (fully triangulated) planar graph is equal to four times the number of edge 3-colorings of its planar cubic dual, this result gives a formula for the number of 4-colorings of a finite maximal planar graph. * **

📜 SIMILAR VOLUMES

On the Number of 3-Edge Colorings of Cub

On the Number of 3-Edge Colorings of Cubic Graphs

✍ Christian Szegedy 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In this paper we present a short algebraic proof for a generalization of a formula of R. Penrose, Some applications of negative dimensional tensors, in: Combinatorial Mathematics and its Applications Welsh (ed.), Academic Press, 1971, pp. 221-244 on the number of 3-edge colorings of a plane cubic gr

Coloring the square of a planar graph

✍ Jan van den Heuvel; Sean McGuinness 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract We prove that for any planar graph __G__ with maximum degree Δ, it holds that the chromatic number of the square of __G__ satisfies χ(__G__^2^) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002

Coloring the Edges of a Complete Graph

✍ Annamaria G. Varga 📂 Article 📅 1972 🏛 John Wiley and Sons 🌐 English ⚖ 577 KB

Edge orientations on cubic graphs with a

Edge orientations on cubic graphs with a maximum number of pairs of oppositely oriented edges

✍ Günther Malle 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 438 KB

We consider the problem: Characterize the edge orienta,tions of a finite graph with a maximum number of pairs of oppositely oriented edges. The probiem is solved for finite cubic graphs.

The edge reconstruction number of a disc

The edge reconstruction number of a disconnected graph

✍ Robert Molina 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 532 KB

On the greatest number of 2 and 3 colori

On the greatest number of 2 and 3 colorings of a (v, e)-graph

✍ Felix Lazebnik 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 446 KB

Let 9 denote the family of simple undirected graphs on u vertices having e edges ( ( u , el-graphs) and P(A, G ) be the chromatic polynomial of a graph G. For the given integers u, e, A, let f b , e, A) denote the greatest number of proper colorings in A or less colors that a (u, e)-graph G can have