• 3
  • 3
  • 82
  • 82
IPM
30
YEARS OLD

“School of Mathematics”

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