Mathematics – Combinatorics
Scientific paper
2010-08-12
Mathematics
Combinatorics
26 pages, 2 figures, 3 tables
Scientific paper
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 [n], and h is an element of [n] not in T. Vertices (h_x,T_x) and (h_y,T_y) are adjacent iff h_x \in T_y, h_y \in T_x, and T_x and T_y 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_{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 \ge 2, and we determine the full automorphism group of H_{n:r}, which is isomorphic to the symmetric group on n elements.
No associations
LandOfFree
Haggkvist-Hell Graphs: A class of Kneser-colorable graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Haggkvist-Hell Graphs: A class of Kneser-colorable graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Haggkvist-Hell Graphs: A class of Kneser-colorable graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-587803