Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-25T06:25:59.525Z Has data issue: false hasContentIssue false
  • English
  • Français

Polyhedral decompositions of cubic graphs

Published online by Cambridge University Press:  17 April 2009

G. Szekeres
G. Szekeres
Affiliation:
School of Mathematics, University of New South Wales, Kensington, New South Wales.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A polyhedral decomposition of a finite trivalent graph G is defined as a set of circuits = {C1, C2, … Cm} with the property that every edge of G occurs exactly twice as an edge of some Ck. The decomposition is called even if every Ck is a simple circuit of even length. If G has a Tait colouring by three colours a, b, c then the (a, b), (b, c) and (c, a) circuits obviously form an even polyhedral decomposition. It is shown that the converse is also true: if G has an even polyhedral decomposition then it also has a Tait colouring. This permits an equivalent formulation of the four colour conjecture (and a much stronger conjecture of Branko Grünbaum) in terms of polyhedral decompositions alone.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 8 , Issue 3 , June 1973 , pp. 367 - 387
Copyright
Copyright © Australian Mathematical Society 1973

References

[1]Berge, Claude, The theory of graphs and its applications (translated by Methuen, Alison Doig, London; John Wiley & Sons, New York; 1962).Google Scholar
[2]Grünbaum, Branko, Conjecture 6, Recent progress in combinatorics, 343 (Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, edited by Tutte, W.T.. Academic Press, New York, London, 1969).Google Scholar
[3]König, D., “Vonalrendszerek kétoldalu felületeken”, Mat. Természettud. Értesitö 29 (1911), 112–117.Google Scholar
[4]König, Dénes, Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe (Mathematik und ihre Auwendung in Monographien und Lehrbüchern, Band 16. Akad. Verlagsges., Leipzig 1936; reprinted: Chelsea, New York, 1950).Google Scholar
[5]Ore, Oystein, The four-color problem (Pure and Applied Mathematics, 27. Academic Press, New York, London, 1967).Google Scholar
[6]Szekeres, G., “Oriented Tait graphs”, J. Austral. Math. Soc. (to appear).Google Scholar
[7]Tutte, W.T., Connectivity in graphs (University of Toronto Press, Toronto, Ontario; Oxford University Press, London; 1966).CrossRefGoogle Scholar