Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T10:50:21.066Z Has data issue: false hasContentIssue false
  • English
  • Français

On Polyhedral Embeddings of Cubic Graphs

Published online by Cambridge University Press:  10 August 2006

BOJAN MOHAR  and
ANDREJ VODOPIVEC
BOJAN MOHAR
Affiliation:
Department of Mathematics, University of Ljubljana, 1000 Ljubljana, Slovenia (e-mail: bojan.mohar@uni-lj.si) Current address: Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada (e-mail: mohar@sfu.ca).
ANDREJ VODOPIVEC
Affiliation:
Department of Mathematics, IMFM, 1000 Ljubljana, Slovenia (e-mail: andrej.vodopivec@fmf.uni-lj.si)
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.

Polyhedral embeddings of cubic graphs by means of certain operations are studied. It is proved that some known families of snarks have no (orientable) polyhedral embeddings. This result supports a conjecture of Grünbaum that no snark admits an orientable polyhedral embedding. This conjecture is verified by computer for all snarks having fewer than 30 vertices. On the other hand, for every non-orientable surface $S$, there exists a non-3-edge-colourable graph which polyhedrally embeds in $S$.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 15 , Issue 6 , November 2006 , pp. 877 - 893
Copyright
2006 Cambridge University Press