On the chromatic number of a subgraph of the Kneser graph
| Authors | |
|---|---|
| Publication date | 2018 |
| Journal | Electronic Notes in Discrete Mathematics |
| Volume | Issue number | 68 |
| Pages (from-to) | 227-232 |
| Organisations |
|
| Abstract | Let n and k be positive integers with n≥2k. Consider a circle C with n points 1,…,n in clockwise order. The interlacing graph IGn,k is the graph with vertices corresponding to k-subsets of [n] that do not contain two adjacent points on C, 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 is equal to n/k, hence the chromatic number is ⌈n/k⌉ and that its independence number is (n−k−1k−1). |
| Document type | Article |
| Language | English |
| Published at |
https://doi.org/10.1016/j.endm.2018.06.039
(Final published version)
|
| Other links | |
| Permalink to this page | |