“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 2347 |
|
||||
| Abstract: | |||||
|
Let F be a graph of order at most k. We prove that for any
integer g there is a graph G of girth at least g and of
maximum degree at most 5k13 such that G admits a surjective
homomorphism c to F, and moreover, for any F-pointed graph
H (see definition below) with at most k vertices, and for any
homomorphism h from G to H there is a unique homomorphism
f from F to H such that h=f °c. As a consequence, we
prove that if H is a projective graph of order k, then for any
finite family F of prescribed mappings from a set X to
V(H) (with |F| = t), there is a graph G of arbitrary
large girth and of maximum degree at most 5k26mt (where m = |X|) such that X ⊆ V(G) and up to an automorphism of
H, there are exactly t homomorphisms from G to H, each of
which is an extension of an f ∈ F.
Download TeX format |
|||||
| back to top | |||||
