Graph homomorphism

DEFINITION A flow diagram P is a graph homomorphic image of flow diagram P under graph homomorphism h, if h is a function from the address set of P ... 

An alternative method of proof uses repeated applications of a local transformation, the duplicate operation, which also preserves graph homomorphic images. Call a direct connection in P from n to m anomalous if n m and n... 

CLAIM Given a flow diagram P we can construct a flow diagram P such that P is a graph homomorphic image of P and a(P ) = 0. ... 

The scheme in Example IV-2 is a graph homomorphic image of this scheme. 

The notions of a subcomplex and simplicial maps are defined for the geometric simplicial complexes in full analogy with the abstract simpficial complexes. These notions then coincide under the described correspondence between the two families of simplicial complexes. Note that when two complexes K and L have dimension less than 2, i.e., can be viewed as graphs, the graph homomorphisms (see Definition 9.20) between K and L are simplicial maps, but not vice versa. 

Proposition 4.24. For arbitrary graphs T and G, their direct product (together with the projection graph homomorphisms) and their categorical product in Graphs coincide. 

Second, the graph homomorphism p is the unique one satisfying the commuting relations, since already the corresponding set map is unique. ... 

A graph homomorphism G —> is the same as a vertex coloring of G with n colors. In particular, the chromatic number of G, denoted by x(G), is the minimal n such that there exists a graph homomorphism p G Kn see Definition 17.2. 

Therefore, as mentioned in Chapter 4, the graphs together with graph homomorphisms form the category Graphs. 

On the intuitive level, one can think of each tj V(T) —> 0 satisfying the conditions of Definition 9.23 as associating nonempty lists of vertices of G to vertices of T with the condition on this collection of lists being that any choice of one vertex from each list will yield a graph homomorphism from T to G. 

For future reference, let us remark that the proofs of Proposition 11.16 and Proposition 11.17 imply that the inclusion graph homomorphism i Lzk C ik+i induces an isomorphism on the homology groups f/ (Ind(h3fc)) ... 

Clearly, for any two positive integers m and n, a graph homomorphism Kn exists if and only if m < n. More generally, we can now restate Definition 17.2 in the language of graph homomorphisms. 

Proof. If G can be colored with n colors, then there exists a graph homomorphism if G Kn- Considering the composition T G Kn, we conclude that T can be colored with n colors as well. ... 

Proof. We establish a bijection between coverings by n independent sets Iij j In such that every point is covered k times and graph homomorphisms... 

Xc G) = inf r, where the infimum is taken over all positive reals r such that there exists a graph homomorphism from G to R. ... 

It will be shown in Theorem 18.3 that the complexes Af G) and Bip (G) have the same simple homotopy type. This fact leads one to consider the family of Horn complexes as a natural context in which to look for further obstructions to the existence of graph homomorphisms. 

The situation is slightly more comphcated if one considers the functoriahty in the first argument. Let us choose some graph homomorphism V from T to G, and let if be some graph. 

Example 18.14- An arbitrary graph homomorphism of loop-free graphs p G G will induce Z2-maps Bip(G) —> Bip(G ) and ... 

---