On the chromatic number of a subgraph of the Kneser graph
| Autor: | Bart Sevenster, Bart Litjens, Lluís Vena, Sven Polak |
|---|---|
| Přispěvatelé: | Algebra, Geometry & Mathematical Physics (KDV, FNWI) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Connected component
Clockwise order Applied Mathematics Kneser graph 010102 general mathematics Chromatic number Polygon Interlacing 0102 computer and information sciences 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics Circular chromatic number Independence number Interlace Discrete Mathematics and Combinatorics Chromatic scale 0101 mathematics Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics, 68, 227-232. Elsevier Electronic Notes in Discrete Mathematics, 68, 227-232 |
| ISSN: | 1571-0653 |
| DOI: | 10.1016/j.endm.2018.06.039 |
| Popis: | Let n and k be positive integers with n ≥ 2 k . Consider a circle C with n points 1 , … , n in clockwise order. The interlacing graph IG n , 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 IG n , k is equal to n / k , hence the chromatic number is ⌈ n / k ⌉ , and that its independence number is ( n − k − 1 k − 1 ) . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect