𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Face 2-Colourable Triangular Embeddings of Complete Graphs

✍ Scribed by M.J. Grannell; T.S. Griggs; Jozef Širáň

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
420 KB
Volume
74
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

A face 2-colourable triangulation of an orientable surface by a complete graph K n exists if and only if n#3 or 7 (mod 12). The existence of such triangulations follows from current graph constructions used in the proof of the Heawood conjecture. In this paper we give an alternative construction for half of the residue class n#7 (mod 12) which lifts a face 2-colourable triangulation by K m to one by K 3m&2 . A nonorientable version of this result is discussed as well which enables us to produce nonisomorphic nonorientable triangular embeddings of K n for half of the residue class n#1 (mod 6). We also note the existence of nonisomorphic orientable triangular embeddings of K n for n#7 (mod 12) and n{7.

📜 SIMILAR VOLUMES

On the number of triangular embeddings o
On the number of triangular embeddings of complete graphs and complete tripartite graphs
✍ M. J. Grannell; M. Knor 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract We prove that for every prime number __p__ and odd __m__>1, as __s__→∞, there are at least __w__ face 2‐colorable triangular embeddings of __K__~__w, w, w__~, where __w__ = __m__·__p__^__s__^. For both orientable and nonorientable embeddings, this result implies that for infinitely many

Triangular embeddings of complete graphs
Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices
✍ M. N. Ellingham; Chris Stephens 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB

In this paper, we describe the generation of all nonorientable triangular embeddings of the complete graphs K 12 and K 13 . (The 59 nonisomorphic orientable triangular embeddings of K 12 were found in 1996 by Altshuler, Bokowski, and Schuchert, and K 13 has no orientable triangular embeddings.) Ther

Face colorings of embedded graphs
Face colorings of embedded graphs
✍ Dan Archdeacon 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB

We characterize those graphs which have at least one embedding into some surface such that the faces can be properly colored in four or fewer colors. Embeddings into both orientable and nonorientable surfaces are considered.

Regular orientable embeddings of complet
Regular orientable embeddings of complete bipartite graphs
✍ Jin Ho Kwak; Young Soo Kwon 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph __K__~__n,n__~ are in one‐to‐one correspondence with the permutations on __n__ elements satisfying a given criterion, and the isomorphism classes of them are com

Simultaneously Colouring the Edges and F
Simultaneously Colouring the Edges and Faces of Plane Graphs
✍ Adrian O. Waller 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 345 KB

In a simultaneous colouring of the edges and faces of a plane graph we colour edges and faces so that every two adjacent or incident pair of them receive different colours. In this paper we prove a conjecture of Mel'nikov which states that for this colouring every plane graph can be coloured with 2+