✦ LIBER ✦

On Diagonally 10-Coloring Plane Triangulations

✍ Scribed by Daniel P. Sanders; Yue Zhao

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 440 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200108

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This article shows that the vertices of a plane triangulation may be colored with 10 colors such that every pair of vertices has different colors if they are either adjacent or diagonal, that is, that they are not adjacent but are adjacent to two faces which share an edge. This improves a result of Borodin, who showed that 11 colors were sufficient. © 1996 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Diagonal 11-coloring of plane triangulat

Diagonal 11-coloring of plane triangulations

✍ Oleg V. Borodin 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## Abstract The vertices of each plane triangulation without loops and multiple edges may be colored with 11 colors so that for every two adjacent triangles [__xyz__] and [__wxy__], the vertices __x__,__y__,__w__,__z__ are colored pairwise differently.

Simultaneous diagonal flips in plane tri

Simultaneous diagonal flips in plane triangulations

✍ Prosenjit Bose; Jurek Czyzowicz; Zhicheng Gao; Pat Morin; David R. Wood 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 468 KB

## Abstract Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with __n__ ≥ 6 vertices has a simultaneous flip into a 4‐connected triangulation, and that the set of edges to be flipped can be computed in $\cal O$(__n__) time. It follows that

On covering bridged plane triangulations

On covering bridged plane triangulations with balls

✍ Victor Chepoi; Yann Vaxès 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract We show that every plane graph of diameter 2__r__ in which all inner faces are triangles and all inner vertices have degree larger than 5 can be covered with two balls of radius __r__. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 65–80, 2003

Diagonal Flips of Triangulations on Clos

Diagonal Flips of Triangulations on Closed Surfaces Preserving Specified Properties

✍ Richard Brunet; Atsuhiro Nakamoto; Seiya Negami 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 445 KB

Consider a class P of triangulations on a closed surface F 2 , closed under vertex splitting. We shall show that any two triangulations with the same and sufficiently large number of vertices which belong to P can be transformed into each other, up to homeomorphism, by a finite sequence of diagonal

Diagonal Flips in Triangulations on Clos

Diagonal Flips in Triangulations on Closed Surfaces with Minimum Degree at Least 4

✍ Hideo Komuro; Atsuhiro Nakamoto; Seiya Negami 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 365 KB

It will be shown that any two triangulations on a closed surface, except the sphere, with minimum degree at least 4 can be transformed into each other by a finite sequence of diagonal flips through those triangulations if they have a sufficiently large and same number of vertices. The same fact hold

Structural theorem on plane graphs with

Structural theorem on plane graphs with application to the entire coloring number

✍ Borodin, Oleg V. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 477 KB 👁 1 views

In 1973, Kronk and Mitchem (Discrete Math. (5) 255-260) conjectured that the vertices, edges and faces of each plane graph G may be colored with D(G) + 4 colors, where D(G) is the maximum degree of G, so that any two adjacent or incident elements receive distinct colors. They succeeded in verifying