On the independence ratio of distance graphs

详细信息    查看全文

• 作者：James M. Carraherp>ap>p> ; p>p>carraherjm2@unk.edu" class="auth_mail" title="E-mail the corresponding authorp> ; David Galvinp>bp>p> ; p>p>dgalvin1@nd.edu" class="auth_mail" title="E-mail the corresponding authorp> ; Stephen G. Hartkep>cp>p> ; p>p>stephen.hartke@ucdenver.edu" class="auth_mail" title="E-mail the corresponding authorp> ; A.J. Radcliffep>dp>p> ; p>p>aradcliffe1@math.unl.edu" class="auth_mail" title="E-mail the corresponding authorp> ; Derrick Stoleep>ep>p> ; p>p>dstolee@iastate.edu" class="auth_mail" title="E-mail the corresponding authorp>
• 关键词：Distance graphs ; Independence ratio ; Fractional chromatic number ; Discharging method
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 December 2016
• 年：2016
• 卷：339
• 期：12
• 页码：3058-3072
• 全文大小：508 K

文摘

A distance graph is an undirected graph on the integers where two integers are adjacent if their difference is in a prescribed distance set. The independence ratio   of a distance graph pan id="mmlsi5" class="mathmlsrc">pan class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301637&_mathId=si5.gif&_user=111111111&_pii=S0012365X16301637&_rdoc=1&_issn=0012365X&md5=a2f01ba9e9724e288c98ccdcf05ad533" title="Click to view the MathML source">Gpan>pan class="mathContainer hidden">pan class="mathCode">$G$pan>pan>pan> is the maximum density of an independent set in pan id="mmlsi5" class="mathmlsrc">pan class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301637&_mathId=si5.gif&_user=111111111&_pii=S0012365X16301637&_rdoc=1&_issn=0012365X&md5=a2f01ba9e9724e288c98ccdcf05ad533" title="Click to view the MathML source">Gpan>pan class="mathContainer hidden">pan class="mathCode">$G$pan>pan>pan>. Lih et al. (1999) showed that the independence ratio is equal to the inverse of the fractional chromatic number, thus relating the concept to the well studied question of finding the chromatic number of distance graphs.p><p id="sp000015">We prove that the independence ratio of a distance graph is achieved by a periodic set, and we present a framework for discharging arguments to demonstrate upper bounds on the independence ratio. With these tools, we determine the exact independence ratio for several infinite families of distance sets of size three and determine asymptotic values for others.