ﻻ يوجد ملخص باللغة العربية
The neighborhood complex of a graph was introduced by Lovasz to provide topological lower bounds on chromatic number, and more general homomorphism complexes of graphs were further studied by Babson and Kozlov. Such `Hom complexes are also related to reconfiguration problems and a notion of discrete homotopy for graphs. Here we initiate the detailed study of Hom complexes for directed graphs, which have applications in the study of graded posets and resolutions of monomial ideals. Our construction can be seen as a special case of the poset structure on the set of multihomomorphisms in more general categories, as introduced by Kozlov, Matsushita, and others. We relate the topological properties of Hom complexes to certain digraph operations including products, adjunctions, and foldings. We introduce a notion of a neighborhood complex for a directed graph and prove that its homotopy type is recovered as a certain Hom complex. We establish a number of results regarding the topology of these complexes, including the dependence on directed bipartite subgraphs, a directed version of the Mycielksi construction, as well as vanishing theorems for higher homology. Inspired by notions of reconfigurations of directed graph colorings we study the connectivity of Hom complexes into tournaments $T_n$. We obtain a complete answer for the case of transitive $T_n$, where we also describe a connection to mixed subdivisions of dilated simplices. Finally we use paths in the internal hom objects of directed graphs to define various notions of homotopy, and discuss connections to the topology of Hom complexes.
The notion of $times$-homotopy from cite{DocHom} is investigated in the context of the category of pointed graphs. The main result is a long exact sequence that relates the higher homotopy groups of the space $Hom_*(G,H)$ with the homotopy groups of
We investigate a notion of $times$-homotopy of graph maps that is based on the internal hom associated to the categorical product in the category of graphs. It is shown that graph $times$-homotopy is characterized by the topological properties of the
A flag complex can be defined as a simplicial complex whose simplices correspond to complete subgraphs of its 1-skeleton taken as a graph. In this article, by introducing the notion of s-dismantlability, we shall define the s-homotopy type of a graph
We introduce new methods for understanding the topology of $Hom$ complexes (spaces of homomorphisms between two graphs), mostly in the context of group actions on graphs and posets. We view $Hom(T,-)$ and $Hom(-,G)$ as functors from graphs to posets,
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $(G,sigma)$, equipped with lists $L(v) subseteq V(H), v in V(G)$, of al