✦ LIBER ✦

Face colorings of embedded graphs

✍ Scribed by Dan Archdeacon

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 498 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080307

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Coloring edges of embedded graphs

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

In this paper, we prove that any graph G with maximum degree ÁG ! 11 p 49À241AEa2, which is embeddable in a surface AE of characteristic 1AE 1 and satis®es jVGj b 2ÁGÀ5À2 p 6ÁG, is class one.

3-Coloring graphs embedded in surfaces

✍ Zhao, Yue 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB 👁 3 views

In this article, we show that there exists an integer k(Σ)

Face 2-Colourable Triangular Embeddings

Face 2-Colourable Triangular Embeddings of Complete Graphs

✍ M.J. Grannell; T.S. Griggs; Jozef Širáň 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 420 KB

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

Coloring Face-Hypergraphs of Graphs on S

Coloring Face-Hypergraphs of Graphs on Surfaces

✍ André Kündgen; Radhika Ramamurthi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 223 KB

The face-hypergraph, H(G), of a graph G embedded in a surface has vertex set V(G), and every face of G corresponds to an edge of H(G) consisting of the vertices incident to the face. We study coloring parameters of these embedded hypergraphs. A hypergraph is k-colorable (k-choosable) if there is a c

Rainbow faces in edge-colored plane grap

Rainbow faces in edge-colored plane graphs

✍ Stanislav Jendrol'; Jozef Miškuf; Roman Soták; Erika Škrabul'áková 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## Abstract A face of an edge‐colored plane graph is called __rainbow__ if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph __G__with no rainbow face is called __the edge‐rainbowness__ of __G__. In this pap

Acrylic improper colorings of graphs

✍ Boiron, P.; Sopena, E.; Vignal, L. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 2 views

In this article, we introduce the new notion of acyclic improper colorings of graphs. An improper coloring of a graph is a vertex-coloring in which adjacent vertices are allowed to have the same color, but each color class V i satisfies some condition depending on i. Such a coloring is acyclic if th