✦ LIBER ✦

Realizing the chromatic numbers of triangulations of surfaces

✍ Scribed by Frank Harary; Serge Lawrencenko; Vladimir Korzhik

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 440 KB
Volume: 122
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90295-5

No coin nor oath required. For personal study only.

✦ Synopsis

Given an orientable or nonorientable closed surface S and an integer n not less than 3 and not greater than the chromatic number of S, we construct a graph admitting a triangular embedding in S and having chromatic number n.

In general we follow the terminology and notation of [3].

📜 SIMILAR VOLUMES

Chromatic numbers of quadrangulations on

Chromatic numbers of quadrangulations on closed surfaces

✍ Dan Archdeacon; Joan Hutchinson; Atsuhiro Nakamoto; Seiya Negam; Katsuhiro Ota 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

## Abstract It has been shown that every quadrangulation on any nonspherical orientable closed surface with a sufficiently large representativity has chromatic number at most 3. In this paper, we show that a quadrangulation __G__ on a nonorientable closed surface __N~k~__ has chromatic number at le

Chromaticity of triangulated graphs

✍ Paul Vaderlind 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

A graph G is called triangulated (or rigid-circuit graph, or chordal graph) if every circuit of G with length greater than 3 has a chord. It can be shown (see, UI, . . . , u,, . Let G = G,.

Realizability of delaunay triangulations

✍ Michael B. Dillencourt 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 702 KB

Circular Chromatic Numbers and Fractiona

Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs

✍ G.J. Chang; L. Huang; X. Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for

Chromatic numbers of subgraphs

✍ F. Galvin 📂 Article 📅 1973 🏛 Springer Netherlands 🌐 English ⚖ 124 KB

Irreducible Triangulations of Surfaces

✍ Z. Gao; R.B. Richter; P.D. Seymour 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 346 KB

In this note we show that, for any surface 7 and any k, there are at most finitely many triangulations of 7 such that each edge is in a noncontractible cycle of length k and is in no shorter noncontractible cycle. Such a triangulation is k-irreducible. This is equivalent to the statement that for an