Häggkvist–Hell graphs: A class of Kneser-colorable graphs

For positive integers nn and rr we define the Häggkvist–Hell graph  , Hn:rHn:r, to be the graph whose vertices are the ordered pairs (h,T)(h,T) where TT is an rr-subset of [n][n], and hh is an element of [n][n] not in TT. Vertices (hx,Tx)(hx,Tx) and (hy,Ty)(hy,Ty) are adjacent iff hx∈Tyhx∈Ty, hy∈Txhy∈Tx, and Tx∩Ty=∅Tx∩Ty=∅. These triangle-free arc transitive graphs are an extension of the idea of Kneser graphs, and there is a natural homomorphism from the Häggkvist–Hell graph, Hn:rHn:r, to the corresponding Kneser graph, Kn:rKn:r. Häggkvist and Hell introduced the r=3r=3 case of these graphs, showing that a cubic graph admits a homomorphism to H22:3H22:3 if and only if it is triangle-free. Gallucio, Hell, and Nes˘etr˘il also considered the r=3r=3 case, proving that Hn:3Hn:3 can have arbitrarily large chromatic number. In this paper we give the exact values for diameter, girth, and odd girth of all Häggkvist–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≥2r≥2, and we determine the full automorphism group of Hn:rHn:r, which is isomorphic to the symmetric group on nn elements.