Fractional Multiples of Graphs and the Density of Vertex-Transitive Graphs |
| |
Authors: | Claude Tardif |
| |
Affiliation: | (1) Département de mathématiques et de statistique, Université de Montréal, C.P. 6128, succ. Centre-ville, Montreal, Québec, H3C 3J7, Canada |
| |
Abstract: | 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. |
| |
Keywords: | fractional chromatic number graph homomorphism |
本文献已被 SpringerLink 等数据库收录! |
|