✦ LIBER ✦

Cyclic degree and cyclic coloring of 3-polytopes

✍ Scribed by Borodin, Oleg V.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 402 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199611)23:3<225::aid-jgt2>3.0.co;2-u

No coin nor oath required. For personal study only.

✦ Synopsis

A vertex coloring of a plane graph is called cyclic if the vertices in each face bounding cycle are colored differently. The main result is an improvement of the upper bound for the cyclic chromatic number of 3-polytopes due to Plummer and Toft, 1987 (J. Graph Theory 11 (1 987) 505-51 7). The proof is based on a structural property of 3-polytopes, in a sense stronger than that implied by Lebesgue's theorem of 1940. Namely, precise upper bound is obtained for the minimum cyclic degree of 3-polytopes with the maximum face Size at least 24.

📜 SIMILAR VOLUMES

Cyclic coloration of 3-polytopes

✍ Michael D. Plummer; Bjarne Toft 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB

A cyclic coloration of a planar graph G is an assignment of colors to the points of G such that for any face bounding cycle the points of f have different colors. We observe that the upper bound 2p\*(G), due to 0. Ore and M. D. Plummer, can be improved to p \* ( G ) + 9 when G is 3connected (p\* den

Subpolytopes of Cyclic Polytopes

✍ Tibor Bisztriczky; Gyula Károlyi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 85 KB

A remarkable result of Shemer [7] states that the combinatorial structure of a neighbourly 2mpolytope determines the combinatorial structure of each of its subpolytopes. From this, it follows that every subpolytope of a cyclic 2m-polytope is cyclic. In this note, we present a direct proof of this co

Cyclic Polytopes and Oriented Matroids

✍ Raul Cordovil; Pierre Duchet 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 244 KB

Consider the moment curve in the real euclidean space R d defined parametrically by the map γ : R → R d , t → γ (t) = (t, t 2 , . . . , t d ). The cyclic d-polytope C d (t 1 , . . . , t n ) is the convex hull of n > d different points on this curve. The matroidal analogs are the alternating oriented

On Subdivision Posets of Cyclic Polytope

On Subdivision Posets of Cyclic Polytopes

✍ Paul H. Edelman; Jörg Rambau; Victor Reiner 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 231 KB

There are two related poset structures, the higher Stasheff-Tamari orders, on the set of all triangulations of the cyclic d polytope with n vertices. In this paper it is shown that both of them have the homotopy type of a sphere of dimension nd -3. Moreover, we resolve positively a new special case

Equitable list-coloring for graphs of ma

Equitable list-coloring for graphs of maximum degree 3

✍ Michael J. Pelsmajer 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract Given lists of available colors assigned to the vertices of a graph __G__, a list coloring is a proper coloring of __G__ such that the color on each vertex is chosen from its list. If the lists all have size __k__, then a list coloring is equitable if each color appears on at most ⌈|__V

Separation of Cyclic GMP and Cyclic AMP

✍ Sonia Villegas; Laurence L. Brunton 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 58 KB