Haggkvist-Hell graphs: A class of Kneser-colorable graphs

For positive integers n and r we define the Haggkvist-Hell graph, H-n:r, to be the graph whose vertices are the ordered pairs (h, T) where T is an r-subset of In I. and h is an element of I n not in T. Vertices (h(x), T-x) and (h(y), T-y) are adjacent iff h(x) is an element of T-y, h(y) is an element of T-x, and T-x boolean AND T-y = empty set. These triangle-free arc transitive graphs are an extension of the idea of Kneser graphs, and there is a natural homomorphism from the Haggkvist-Hell graph, H-n:r, to the corresponding Kneser graph, K-n:r. Haggkvist and Hell introduced the r = 3 case of these graphs, showing that a cubic graph admits a homomorphism to H-22:3 if and only if it is triangle-free. Gallucio, Hell, and Nesetril also considered the r = 3 case, proving that H-n:3 can have arbitrarily large chromatic number. In this paper we give the exact values for diameter, girth, and odd girth of all Haggkvist-Hell graphs, and we give bounds for independence, chromatic, and fractional chromatic number. Furthermore, we extend the result of Gallucio et al. to any fixed r >= 2, and we determine the full automorphism group of H-n:r, which is isomorphic to the symmetric group on n elements. (C) 2011 Elsevier BM. All rights reserved.