“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 2347
School of Mathematics
  Title:   Sparse H-colourable graphs of bounded maximum degree
1.  H. Hajiabolhassan
2.  X. Zhu
  Status:   Published
  Journal: Graphs Combin.
  Vol.:  20
  Year:  2004
  Pages:   65-71
  Supported by:  IPM
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 XV(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 fF.

Download TeX format
back to top
scroll left or right