JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 10, No 1 (1999)

Claude Tardif

We introduce a construction called the fractional multiple of a graph. This construction is used to settle a question raised by E. Welzl: We show that if G and H are vertex-transitive graphs such that there exists a homomorphism from G to H but no homomorphism from H to G, then there exists a vertex-transitive graph that is homomorphically in between G and H.

M.O. Albertson and V. Booth, Homomorphisms of symmetric graphs, Proceedings of the 17th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL., 1986, Congr. Numer. 53 (1986), 79-86. M.O. Albertson and K.L. Collins, Homomorphisms of 3-chromatic graphs, Discrete Math. 54 (1985), 127-132. J.A. Bondy and P. Hell, A note on the star chromatic number, J. Graph Theory 14 (1990), 479-482. G. Hahn, P. Hell, and S. Poljak, On the ultimate independence ratio of a graph, European J. Combin. 16 (1995), 253-261. G. Hahn and C. Tardif, Graph homomorphisms: Structure and symmetry, Graph symmetry (Montreal, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 1997, Vol. 497, pp. 107-166. D.J. Miller, The categorical product of graphs, Canad. J. Math. 20 (1968), 1511-1521. J. Ne et il, Structure of graph homomorphisms I, to appear in Proceedings of Matrahaza Meeting, V.T. Sos (Ed.),
1996. J. Ne et il and X. Zhu, Path homomorphisms, Math. Proc. Cambridge Philos. Soc. 120 (1996), 207-220. S. Stahl, $n$-tuple colorings and associated graphs, J. Combinatorial Theory Ser. B 20 (1976), 185-203. E. Welzl, Color-families are dense, J. Theoret. Comput. Sci. 17 (1982), 29-41. E. Welzl, Symmetric graphs and interpretations, J. Combinatorial Theory Ser. B 37 (1984), 235-244.