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

Original · EN

For positive integers n and r we define the Haggkvist-Hell graph, Hₙ:ᵣ, to be the graph whose vertices are the ordered pairs (h,T) where T is an r-subset of [n], and h is an element of [n] not in T. Vertices (hₓ,Tₓ) and (hy,Ty) are adjacent iff hₓ ∈ Ty, hy ∈ Tₓ, and Tₓ and Ty are disjoint. 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ₙ:ᵣ, to the corresponding Kneser graph, Kₙ:ᵣ. Haggkvist and Hell introduced the r=3 case of these graphs, showing that a cubic graph admits a homomorphism to H₂₂:₃ if and only if it is triangle-free. Gallucio, Hell, and Nesetril also considered the r=3 case, proving that Hₙ:₃ 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ₙ:ᵣ, which is isomorphic to the symmetric group on n elements.