Universal coverings of PL-manifolds via coloured graphs

Summary By means of techniques and results concerning maps on surfaces [JS] and edge-coloured graphs representing PL-manifolds [FGG], we prove the existence of an infinite ball complexP(n), n > 1, such thatevery orientable PL-manifold of dimension n is a quotient of |P(n)| by the action of a finite index subgroup of a Fuchsian group with signature ,with h(2) = h(3) = 4 and h(n) = 2, for n > 3. The core of the proof is that all orientable PL-manifolds of dimensionn can be represented by edge-coloured graphs which are quotients of a universal graph, only depending onn.     

Hom complexes and hypergraph colorings

Babson and Kozlov (2006) [2] studied Hom-complexes of graphs with a focus on graph colorings. In this paper, we generalize Hom-complexes to r-uniform hypergraphs (with multiplicities) and study them mainly in connection with hypergraph colorings. We reinterpret a result of Alon, Frankl and Lovász (1986) [1] by Hom-complexes and show a hierarchy of known lower bounds for the chromatic numbers of r-uniform hypergraphs (with multiplicities) using Hom-complexes.     

Computing the genus of the 2-amalgamations of graphs

The above authors [2] and S. Stahl [3] have shown that if a graphG is the 2-amalgamation of subgraphsG ₁ andG ₂ (namely ifG=G ₁∪G ₂ andG ₁∩G ₂={x, y}, two distinct points) then the orientable genus ofG,γ(G), is given byγ(G)=γ(G ₁)+γ(G ₂)+ε, whereε=0,1 or −1. In this paper we sharpen that result by giving a means by whichε may be computed exactly. This result is then used to give two irreducible graphs for each orientable surface.     

A characterization of planar graphs by trémaux orders

A new characterization of planar graphs is stated in terms of an order relation on the vertices, called the Trémaux order, associated with any Trémaux spanning tree or Depth-First-Search Tree. The proof relies on the work of W. T. Tutte on the theory of crossings and the Trémaux algebraic theory of planarity developed by P. Rosenstiehl.     

Hyperbolic spatial graphs in 3-manifolds

For any closed connected orientable 3-manifold M, we present a method for constructing infinitely many hyperbolic spatial embeddings of a given finite graph with no vertex of degree less than two from hyperbolic spatial graphs in S³ via the Heegaard splitting theory. These spatial embeddings are adjustable so as to take cycle subgraphs into specified homotopy classes of loops in M.     

Star clusters in independence complexes of graphs

We introduce the notion of star cluster of a simplex in a simplicial complex. This concept provides a general tool to study the topology of independence complexes of graphs. We use star clusters to answer a question arisen from works of Engström and Jonsson on the homotopy type of independence complexes of triangle-free graphs and to investigate a large number of examples which appear in the literature. We present an alternative way to study the chromatic and clique numbers of a graph from a homotopical point of view and obtain new results regarding the connectivity of independence complexes.     

On the vertex group of n-manifolds

In this paper we obtain the decomposition of the vertex group of n-manifolds, extending the one given by Kauffman and Lins for dimension 3 and solving the related conjecture. The result is obtained in the more general category of gems: the vertex group of a gem , representing an n-manifold M, is the free product of n copies of the fundamental group of M and a free group F of rank N–n, where N is the number of n-residues of . In particular, for crystallizations FZ and consequently the vertex group is an invariant of M.     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .     

On automorphisms of infinite graphs with forbidden subgraphs

LexX be anm-connected infinite graph without subgraphs homeomorphic toKm, n, for somen, and let α be an automorphism ofX with at least one cycle of infinite length. We characterize the structure of α and use this characterization to extend a known result about orientation-preserving automorphisms of finite plane graphs to infinite plane graphs. In the last section we investigate the action of α on the ends ofX and show that α fixes at most two ends (Theorem 3.2).     

On the knot complement problem for non-hyperbolic knots

This paper explicitly provides two exhaustive and infinite families of pairs (M,k), where M is a lens space and k is a non-hyperbolic knot in M, which produces a manifold homeomorphic to M, by a non-trivial Dehn surgery. Then, we observe the uniqueness of such knot in such lens space, the uniqueness of the slope, and that there is no preserving homeomorphism between the initial and the final M's. We obtain further that Seifert fibered knots, except for the axes, and satellite knots are determined by their complements in lens spaces. An easy application shows that non-hyperbolic knots are determined by their complement in atoroidal and irreducible Seifert fibered 3-manifolds.     

Representing products of manifolds by edge-coloured graphs: the boundary case

In this paper we generalize the construction - introduced by Gagliardi and Grasselli in the closed case - of a coloured-graph representing the product of two manifolds, starting by two coloured graphs representing the manifolds themselves, to the boundary case. In particular we study the genus of the graph product of low dimensional manifold ( resp. n-spheres ) with m-disks. Received September 28, 1998; in final form January 5, 2000 / Published online October 11, 2000     

Barycentric systems and stretchability

Using a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least three free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible.     

The Locally Connected Compact Metric Spaces Embeddable In The Plane

We prove that a 2-connected, locally connected, compact topological space M is homeomorphic to a subset of the 2-sphere if and only if M is metrizable and contains none of the Kuratowski graphs K ₅ and K _3,3.     

Classification Of Locally 2-Connected Compact Metric Spaces

The aim of this paper is to prove that, for compact metric spaces which do not contain infinite complete graphs, the (strong) property of being locally 2-dimensional is guaranteed just by a (weak) local connectivity condition. Specifically, we prove that a locally 2-connected, compact metric space M either contains an infinite complete graph or is surface like in the following sense: There exists a unique surface S such that S and M contain the same finite graphs. Moreover, M is embeddable in S, that is, M is homeomorphic to a subset of S.     

On the height of 2-component links

Let p be a prime and let L be a 2-component link in S³. We define a numerical invariant, called p-height of L, using a tower of successive p-fold branched cyclic coverings of L, and show, in particular, 2-height is algorithmically determined for any 2-component link. Some relationships between p-height and known link type invariants are also established.     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

Partition functions and a generalized coloring‐flow duality for embedded graphs

Let G be a finite group and a class function. Let be a directed graph with for each vertex a cyclic order of the edges incident to it. The cyclic orders give a collection F of faces of H. Define the partition function , where denotes the product of the κ‐values of the edges incident with v (in cyclic order), where the inverse is taken for edges leaving v. Write , where the sum runs over irreducible representations λ of G with character and with for every λ. When H is connected, it is proved that , where 1 is the identity element of G. Among the corollaries, a formula for the number of nowhere‐identity G‐flows on H is derived, generalizing a result of Tutte. We show that these flows correspond bijectively to certain proper G‐colorings of a covering graph of the dual graph of H. This correspondence generalizes coloring‐flow duality for planar graphs.     

Pfaffian labelings and signs of edge colorings

We relate signs of edge-colorings (as in classical Penrose’s result) with “Pfaffian labelings”, a generalization of Pfaffian orientations, whereby edges are labeled by elements of an Abelian group with an element of order two. In particular, we prove a conjecture of Goddyn that all k-edge-colorings of a k-regular Pfaffian graph G have the same sign. We characterize graphs that admit a Pfaffian labeling in terms of bricks and braces in their matching decomposition and in terms of their drawings in the projective plane. Partially supported by NSF grants 0200595 and 0354742.