Structure of Graph Homomorphisms
Roman Bačík · Summit (Simon Fraser University) · 1997
In this thesis we study finite graphs and graph homomorphisms from both, a theoretical and a practical view point. A homomorphism between two graphs G and H is a function from the vertex set of G to the vertex set of H , which maps adjacent vertices of G to adjacent vertices of H. In the first part of this thesis we study homomorphisms, which are equitable. Suppose we have a fixed graph H. An equitable 11-coloring of a graph G is a homomorphism from G to H such that the preimages of vertices of H have almost the same size (they differ by at most one). We consider the complexity of the following problem: INSTANCE: A graph G. QUESTION: Does G admit an equitable 11-coloring? We give a complete characterization of the complexity of the equitable If-coloring problem. In particular, we show that the problem is polynomial if I1 is a disjoint union of complete bipartite graphs, and it is NP-complete otherwise. To get a better insight into a combinatorial problem, one often studies relaxations of the problem. The second part of this thesis deals with relaxations of graph homomorphisms. In particular, we define a fractional homomorphism and a pseudohomomorphism as natural relaxations of graph homomorphism. We show that our pseudo-homomorphism is equivalent to a semidefinite relaxation, defined by Feige and LovAsz. We also show that there is a simple forbidden subgraph characterization for our fractional homomorphism (the forbidden subgraphs are cliques). As a byproduct, we obtain a simpler proof of the NP-hardness of the fractional chromatic number, a result which was first proved by Grotschel, Lovrisz and Schrijver using the ellipsoid method. We also briefly discuss how to apply these results to the directed case. In the last part of this thesis we consider equivalence classes of graphs under the following equivalence: two graphs G and H are equivalent, if there exist homomorphisms from G to N and from H to G. We study the multiplicative structure of these equivalence classes, and give a necessary and sufficient condition for the existence of a finite factorization of a class into irreducible elements. We also relate this problem to some graph theoretic conjectures concerning graph product.