2018/03/12 by Bart Litjens, Sven Polak, Litjens, Bart +5
Computer Science · Mathematics · #05C15 #05C69 #52B11 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1803.04342
openalex publication_date 2018/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let n,k,r be positive integers with n ≥ rk and r ≥ 2. Consider a circle C with~n points~1,…,n in clockwise order. The r-stable interlacing graph IGn,k(r) is the graph with vertices corresponding to k-subsets S of \1,...,n\ such that any two distinct points in~S have distance at least~r around the circle, and edges between~k-subsets P and Q if they interlace: after removing the points in~P from C, the points in~Q are in different connected components. In this paper we prove that the circular chromatic number of IGn,k(r) is equal to n/k (hence the chromatic number is \lceil n/k \rceil) and that its circular clique number is also n/k . Furthermore, we show that its independence number is \binomn-(r-1)k-1k-1, thereby strengthening a result by Talbot.