On Cylindrical Graph Construction and its Applications
Keywords:
Graph homomorphism, Cylindrical construction, Generalized Petersen graph, Generalized Mycielski construction, Coxeter-like graphs, Adjoint functor, Category of graphs, Labeled and marked graphs, Extremal problems
Abstract
In this article we introduce the cylindrical construction, as an edge-replacement procedure admitting twists on both ends of the hyperedges, generalizing the concepts of lifts and Pultr templates at the same time. We prove a tensor-hom duality for this construction and we show that not only a large number of well-known graph constructions are cylindrical but also the construction and its dual give rise to some new graph constructions, applications and results. To show the applicability of the main duality we introduce generalized Grötzsch, generalized Petersen-like and Coxeter-like graphs and we prove some coloring properties of these graphs.