Asymptotic Clique Covering Ratios of Distance Graphs

✍ Scribed by Daphne D.-F Liu; Xuding Zhu

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 126 KB
• Volume: 23
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.2001.0560

✦ Synopsis

Given a finite set D of positive integers, the distance graph G(Z , D) has Z as the vertex set and {i j : |i -j| ∈ D} as the edge set. Given D, the asymptotic clique covering ratio is defined as S(D) = lim sup n→∞ n cl(n) , where cl(n) is the minimum number of cliques covering any consecutive n vertices of G(Z , D). The parameter S(D) is closely related to the ratio sp T (G) χ (G) of a graph G, where χ(G) and sp T (G) denote, respectively, the chromatic number and the optimal span of a T -coloring of G. We prove that for any finite set D, S(D) is a rational number and can be realized by a 'periodical' clique covering of G(Z , D). Then we investigate the problem for which sets D the equality S(D) = ω(G(Z , D)) holds. (In general, S(D) ≤ ω(G(Z , D)), where ω(G) is the clique number of G.) This problem turns out to be related to T -colorings and to fractional chromatic number and circular chromatic number of distance graphs. Through such connections, we shall show that the equality S(D) = ω(G(Z , D)) holds for many classes of distance graphs. Moreover, we raise questions regarding other such connections.