首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)
Authors:Email author" target="_blank">Seog-Jin?KimEmail author  Kittikorn?Nakprasit
Institution:(1) Department of Mathematics, University of Illinois, Urbana, IL 61801, USA
Abstract:The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that chi(K2(2k+1, k))le4k when k is odd and chi(K2(2k+1, k))le4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on chi(K2(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003
Keywords:Kneser graph  Square  Graph coloring  Intersecting family
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号