✦ LIBER ✦

Cyclic coloration of 3-polytopes

✍ Scribed by Michael D. Plummer; Bjarne Toft

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 418 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110407

No coin nor oath required. For personal study only.

✦ Synopsis

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* denotes the size of a maximum face). The proof uses two principal tools: the theory of Euler contributions and recent results on contractible lines in 3-connected graphs by K. Ando, H. Enomoto and A. Saito.

📜 SIMILAR VOLUMES

Cyclic degree and cyclic coloring of 3-p

Cyclic degree and cyclic coloring of 3-polytopes

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

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

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

Fiber Polytopes for the Projections betw

Fiber Polytopes for the Projections between Cyclic Polytopes

✍ Christos A. Athanasiadis; Jesús A. De Loera; Victor Reiner; Francisco Santos 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 359 KB

The cyclic polytope C (n, d) is the convex hull of any n points on the moment curve {(t, t 2 , . . . , t d ) : we consider the fiber polytope (in the sense of Billera and Sturmfels [6]) associated to the natural projection of cyclic polytopes π : C(n, d ) → C(n, d) which 'forgets' the last dd coord

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

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

The Generalized Baues Problem for Cyclic

The Generalized Baues Problem for Cyclic Polytopes I

✍ Jörg Rambau; Francisco Santos 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 278 KB

An important special case of the generalized Baues problem asks whether the order complex of all proper polyhedral subdivisions of a given point configuration, partially ordered by refinement, is homotopy equivalent to a sphere. In this paper, an affirmative answer is given for the vertex sets of cy