×

A short treatise of spinal quadrangulations. (English) Zbl 1257.05072

This article introduces a new method, called the spinal method, for generating quadrangulations of closed orientable surfaces with given properties. Those surfaces arise as the thickenings of certain spatial graphs called the spines. The properties of spinal quadrangulations are determined by their spines. The proposed method is found to be handier compared to the method of current graphs which was previously used. Many new minimal (with respect to the number of vertices, or faces) quadrangulations with given genus are discovered, in addition to the ones already found by N. Hartsfield and G. Ringel [J. Comb. Theory, Ser. B 46, No. 1, 84–95 (1989; Zbl 0665.05006)].
A new homology formula is obtained as a byproduct. A curved \(d\)-polyhedron \(|K|\) is the (non-PL) embedded image in \(\mathbb{R}^n\) of a simplicial complex \(K\) with dimension \(d \leq n-1.\) Let \(N^n (|K|)\) denote a closed regular neighborhood of \(|K|\) and let \(\beta_k (|K|)\) designates the \(k\)-th Betti number of \(|K|.\) The following formula is provided with rational coefficients for each integer \(k\) (\(0 \leq k \leq n-1)\): \(\beta_k (\partial N^n (|K|)) = \beta_k (|K|) + \beta_{n-k-1}(|K|)\).
Another byproduct is the following optimization result: The maximum chromatic number \(n\) of a graph with first Betti number not exceeding a given value \(g\) is attained by the largest complete graph \(K_n\) with \(\beta_1 (K_n) \leq g\).

MSC:

05C35 Extremal problems in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
90C27 Combinatorial optimization
57Q40 Regular neighborhoods in PL-topology
57M15 Relations of low-dimensional topology with graph theory
52B70 Polyhedral manifolds

Citations:

Zbl 0665.05006
PDFBibTeX XMLCite