Topics in Combinatorics and Graph Theory

Graph Theory is a part of discrete mathematics characterized by the fact of an extremely rapid development during the last 10 years. The number of graph theoretical paper as well as the number of graph theorists increase very strongly. The main purpose of this book is to show the reader the variety of graph theoretical methods and the relation to combinatorics and to give him a survey on a lot of new results, special methods, and interesting informations. This book, which grew out of contributions given by about 130 authors in honour to the 70th birthday of Gerhard Ringel, one of the pioneers in graph theory, is meant to serve as a source of open problems, reference and guide to the extensive literature and as stimulant to further research on graph theory and combinatorics.

On the Problem of Relative Components of Minimal Graphs.- Irregular Assignments and Two Problems á la Ringel.- A Recursive Bound for the Number of Complete K-Subgraphs of a Graph.- One-Factorizations of Tensor Products of Graphs.- Non-Commutative Geometry and Graphs.- The Complexity of the Graph Embedding Problem.- Helly Theorems for Dismantlable Graphs and Pseudo-Modular Graphs.- On the Level-Oriented Two-Dimensional Packing with Rotation of the Rectangles.- On Planar Tilings with Finitely Many Sorts of Tiles.- Examples of Space-Tiling Polyhedra Related to Hilbert’s Problem 18, Question 2.- The Historical Background to Gerhard Ringel’s Work.- Around Three Lemmas in Hamiltonian Graph Theory.- A Note on Metric Properties of Infinite Graphs.- Automotphism Groups of Directed Cayley Graphs.- Triangular Embeddings of Tensor Products of Graphs.- Computing Light Edges in Planar Graphs.- On the Domination Problem for Bipartite Graphs.- Polyhedral Maps with Few Edges.- Aut Gm,n for the Hasse Graph Gm,n of the Subword Poset Bm,n of an m-Ary Cyclic Word of Length n.- Status of Graceful Tree Conjecture in 1989.- Embedded Graphs, Facial Colorings, and Double Cycle Covers.- On Peripheral Vertices in Graphs.- The Vertex-Degrees of Steiner Minimal Trees in Minkowski Planes.- Unfolding Weighted Concensus Orders into Consistent Numerical Scales.- Forbidden Ordered Subgraphs.- On Normal Tournaments with the Least Number of 3-Cycles.- Two-Irregular Graphs.- Cell Complexes and Lower Bounds in Computational Geometry.- Characterizing Directed Postman Tours.- Some Properties of “Almost All” Functions from pk.- Composition of Facets of the Clique Partitioning Polytope.- Optimal Edge-Numbering of Binary Trees.- On Independent Vertices and Edges of a Graph.- The Outerthickness & Outercoarseness of Graphs I. the Complete Graph & the n-Cube.- On Some Graphic Aspects of Addition Theorems.- On the Circumference of Regular Polyhedral Graphs.- Longest Cycles in Circulant Graphs.- Spanning Trees of the Complete Bipartite Graph.- A Combinatorial Theorem Which is Related to the Invariance of the Separating Set for the Plane.- On Certain Trees in Hypercubes.- Extending Hall’s Theorem.- On the Coupling Condition and Hamiltonicity.- Transversals and Matroids.- Classification and Construction of Geodetic Block with Diameter Two.- Graph Distances and Similarity.- Witt Rings and Semiorderings of Planar Ternary Rings.- Linear Inequalities Describing the Class of Intersecting Sperner Families of Subsets, I.- Integral Drawings of the Complete Graph K6.- On Certain Binomial Sums.- Colouring of Spider Graphs.- A Las-Vergnas Type Theorem for Trees.- Quick Gossiping by Multi-Telegraphs.- Numberings on Graphs Having Small Edge Weights.- On Vertexminimal Graphs with Radius r and Connectivity 2m.- Embedding Schemes and the Jordan Curve Theorem.- Subgraph Packing ― A Survey.- On the Radius of Random Subgraphs of the n-Cube.- A Result in Combinatorial Matroid Theory.- On Graphs Embeqdable with Short Faces.- On Cyclic Representations of Triples by Pairs.- On the Steiner Periphery and Steiner Eccentricity of a Graph.- Cycles Containing Three Consecutive Edges in 2k-Edge-Connected Graphs.- Graph Distance and Euclidean Distance on the Grid.- About the Complexity of Some Homomorphism Problems on Graphs.- On an Inequality of Sperner.- Counting Perfect Matchings in Lattice Graphs.- Genus ― Minimal Edges and Kuratowski Subgraphs of a Graph.- From Tree Path-Factors and Doubly Exponential Sequences to a Binomial Inequality.- A Characterization of Point-Colour-Symmetric Hypergraphs.- A Linear Algorithm for the Pathwidth of Trees.- The Time Travelling Problem.- An Aperiodic Triple of Prototiles.- Representation of Graphs by Integers.- Special Systems of Linear Equations and Graphs of Convex Polytopes.- On 2-Embeddable Graphs.- On an Application of the Boolean Differential Calculus to Digital System Theory.- Equtareal Sets in Rd.- On the Piaget Graph.- On a Characterization of Closure Operators by Identities on Semigroups.- Symmetries of Group-Triangulations.- Experimental Mathematics ― Tesselations of Convex Polygons in a Hexagonal Lattice.- Domination in Cubic Graphs.- A Generalization of the Bodendiek Conjecture About Graceful Graphs.- A Sparse callai-Witt Theorem.- Edges with at Most One Crossing in Drawings of the Complete Graph.- Long Cycles in Graphs with Moderate Connectivity.- Independent Covers in Plane Graphs.- List of Contributors.