کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648200 1342398 2012 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Häggkvist–Hell graphs: A class of Kneser-colorable graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 5, 6 March 2012, Pages 837–853
نویسندگان
,