✦ LIBER ✦

A note on graphs and sphere orders

✍ Scribed by Edward R. Scheinerman

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 304 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170303

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A partially ordered set P is called a k‐sphere order if one can assign to each element a ∈ P a ball B~a~ in R^k^ so that a < b iff B~a~ ⊂ B~b~. To a graph G = (V,E) associate a poset P(G) whose elements are the vertices and edges of G. We have v < e in P(G) exactly when v ∈ V, e ∈ E, and v is an end point of e. We show that P(G) is a 3‐sphere order for any graph G. It follows from E. R. Scheinerman [“A Note on Planar Graphs and Circle Orders,” SIAM Journal of Discrete Mathematics, Vol. 4 (1991), pp. 448–451] that the least k for which G embeds in R^k^ equals the least k for which P(G) is a k‐sphere order. For a simplicial complex K one can define P(K) by analogy to P(G) (namely, the face containment order). We prove that for each 2‐dimensional simplicial complex K, there exists a k so that P(K) is a k‐sphere order. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Note on hypergraphs and sphere orders

✍ Alexander Schrijver 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

## Abstract We show that each partial order ≤ of height 2 can be represented by spheres in Euclidean space, where inclusion represents ≤. If each element has at most __k__ elements under it, we can do this in 2__k__ − 1‐dimensional space. This extends a result (and a method) of Scheinerman for the

A Note on Graph Colorings and Graph Poly

A Note on Graph Colorings and Graph Polynomials

✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

A note on graphs spanned by Eulerian gra

A note on graphs spanned by Eulerian graphs

✍ W. R. Pulleyblank 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 1 views

## Abstract We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP‐complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at

A note on regular Ramsey graphs

✍ Noga Alon; Sonny Ben-Shimon; Michael Krivelevich 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 81 KB

## Abstract We prove that there is an absolute constant __C__>0 so that for every natural __n__ there exists a triangle‐free __regular__ graph with no independent set of size at least \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle